C. Tree Division
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree of $$$n$$$ nodes, the i-th node has value $$$a_i$$$.

Define a node $$$t$$$ is valid, if you can divide the $$$n$$$ nodes into two sets $$$A$$$ and $$$B$$$, such that the following condition would hold:

  • $$$\forall u,v\in A(u\neq v)$$$, if $$$u$$$ is on the path from $$$t$$$ to $$$v$$$, then $$$a_u \lt a_v$$$
  • $$$\forall u,v\in B(u\neq v)$$$, if $$$u$$$ is on the path from $$$t$$$ to $$$v$$$, then $$$a_u \gt a_v$$$

You need to find out whether the node $$$1$$$ is valid.

Input

The first line contains one integer $$$n(1\le n\le 10^5)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n(1\le a_i\le n)$$$.

The next $$$n−1$$$ lines each contains two integers $$$x$$$ and $$$y$$$ $$$(1\le x,y\le n)$$$, denoting an edge between node $$$x$$$ and $$$y$$$.

Output

Output YES if node $$$1$$$ is valid, otherwise print NO.

Examples
Input
8
8 1 4 2 5 6 3 7
3 7
5 3
2 4
5 2
6 5
8 6
1 8
Output
YES
Input
6
4 2 1 5 3 1
1 2
2 3
3 4
4 5
1 6
Output
NO
Note

In this case, node $$$1$$$ is valid.

A possible division is: $$$A=\{2,3\}$$$,$$$B=\{1,4,5,6,7,8\}$$$.