Junji has found a beautiful tree lying on the ground, and he wants to take it home to beautify his house. However, he only plans on taking a segment of the tree because he has aichmophobia and too many branches scares him.

The tree has ~N~ connection points. Each connection point has a strength, ~y_i~. A good segment is a segment of the tree where every connection point on the segment has a strength that has a solution to ~x^2 + x = y_i~ for some integer ~x~. A segment of the tree is a path of the tree where every connection point is used at most once. Junji wants the longest good segment to bring home to beautify his house. Note that the longest good segment may be the entire tree, in which case he will take the entire tree home.

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 10^5)~, the number of connection points.

The second line will contain ~N~ integers, ~y_1, y_2, \dots, y_N~ ~(1 \le y_i \le 10^{16})~, the strength of each connection point.

The next ~N-1~ lines will each contain two integers ~a, b~ ~(1 \le a,b \le N)~, meaning that connection point ~a~ and connection point ~b~ are connected by a single branch.

It is guaranteed that there is exactly one path between any two connection points.

Output Specification

Output the number of connection points in the longest good segment in the tree.

Constraints

Subtask 1 [10%]

All connection points satisfy the constraint ~x^2 + x = y_i~ for some integer ~x~.

Subtask 2 [20%]

~y_i \le 10^6~

Subtask 3 [70%]

No additional constraints.

Sample Input 1

7
6 2 30 20 90 42 2
1 2
2 3
3 4
3 5
2 6
2 7

Sample Output 1

4

Sample Input 2

8
2 9999999900000000 3 3 3 3 3 1
1 2
1 3
3 4
4 5
3 6
2 7
2 8

Sample Output 2

2