Problem Description

You are given a binary tree with n nodes. You need to find the length of the longest slide possible in the tree.

Slide is a path from one node to another node where it is possible to reach one node from the other node by only traversing through either left child nodes or right child nodes.

Example $-$

image

Let two node be $2$ and $10.$ Staring from $2$ and only traversing through right child nodes we can reach $10.2->5->8->10.$

Another slide would be $1$ to $4.$ Staring from $1$ and only traversing through left child nodes we can reach $4.1->2->4.$

And $1$ to $5$ is not a slide as $5$ can not be reached from $1$ by only traversing left child nodes or right child nodes.

Length of a slide is equal to the number of edges in the slide. For example in $2->5->8->10$ there are $3$ edges, so the length of the slide from $2$ to $10$ is $3.$

Input format

First line contains an integer n $-$ Number of nodes. Second line contains n space separated integers $-$ The value of nodes. Next n lines contain $3$ space separated integers i$,$ l$,$ r describing the left and right child of ith node as l and r respectively.

Output format

Output the length of the longest slide. If no slide is possible print $0.$

Sample Input $1$

$10$

$2146341523356577254$

$123$

$245$

$36-1$

$4-1-1$

$578$

$6-1-1$

$7-1-1$

$8910$

$9-1-1$

$10-1-1$

Sample Output $1$

$3$

Explanation

The binary tree :$-$

image

Longest slide $-46->23->7->54.$ Length $=3$

Constraints

$0<$ n $<=10^50<$ Value of nodes $<=10^9$