## Valid BST

Points: 100
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C++, Java, Python

You are given a binary trees $$T$$ with $$N$$ nodes.

Check whether $$T$$ is a valid binary search tree (BST).

A valid BST is defined as follows:

• Value of all the nodes in left subtree must be smaller than the value of node.
• Value of all the nodes in right subtree must be greater than the value of node.
• Both the left and right subtrees must also be binary search trees.

#### Input

First line contains single integer: $$N$$.

Following lines of input describe the $$T$$.

First line contains single integer : $$root$$

Next line contains $$N$$ integers, where $$i^{th}$$ integer is the value of the node with index $$i$$.

Next $$N$$ lines contains two integers each, index of left child and right child of node with index $$i$$. If any of integer is $$-1$$ then corresponding child is absent.

#### Output

Output YES if $$T$$ is valid BST, otherwise NO.

#### Constraints

$$1$$ $$\leq$$ $$N$$ $$\leq$$ $$10^5$$

##### Example

Input

3
2
1 2 3
-1 -1
1 3
-1 -1

Output

YES

Note

You can use this template to submit the solution.

## Comments

There are no comments at the moment.