現在有一棵 \(n\) 個點且節點 \(1\) 為根節點的有根樹。

對於 \(i=1,2,...,n\)，節點 \(i\) 的權重是 \(w_i\)。

一個長度為 \(m\) 的數列 \((i_1,i_2,...,i_m)\) 為遞增節點列，若它滿足以下兩個條件：

(1) 對於所有 \(1\le j<m\)，節點 \(i_j\) 為節點 \(i_{j+1}\) 的祖先。

(2) \(w_{i_1}\le w_{i_2}\le\cdots\le w_{i_m}\)。

請問最長的遞增節點列有多長？

Input

第一行輸入一個正整數 \(n\)。

\(2\le n\le 2\cdot10^5\)

第二行輸入 \(n\) 個整數 \(w_1,w_2,...,w_n\)。

\(-10^9\le w_i\le 10^9\)

接下輸入 \(n-1\) 行，第 \(i\) 行輸入兩個正整數 \(u_i,v_i\)，代表第 \(i\) 條邊的兩個端點。

\(1\le u_i,v_i\le n,u_i\neq v_i\)。

保證輸入的圖是一棵樹。

Output

輸出一個正整數，代表最長遞增節點列的長度。

Constraints

第 \(1\) 組測資, \(w_1=w_2=...=w_n\)。 \((10\text{%})\)

第 \(2\) 組測資, \(n\le 5000\) 且 \(u_i=i,v_i=i+1\)。 \((20\text{%})\)

第 \(3\) 組測資, \(n\le 5000\)。 \((20\text{%})\)

第 \(4\) 組測資, \(u_i=i,v_i=i+1\)。 \((25\text{%})\)

第 \(5\) 組測資, 沒有其他限制。\((25\text{%})\)

Sample Input 1

7
1 5 2 4 3 2 4
1 2
2 3
3 4
4 5
5 6
6 7

Sample Output 1

4

Sample Input 2

10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10

Sample Output 2

5