## Valid BST

Submit solution

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