You are given a rooted tree of $N$ vertices where each vertex $v_1$ through $v_ N$ is labeled with a non-negative integer $u_1$ through $u_ N$. The vertex $v_1$ is the root.
Define a “jumping path” within the tree to be a sequence $a_1, a_2, \ldots , a_ k$ of length $k$ where $v_{a_ i}$ is an ancestor of $v_{a_ j}$ for all $1 \le i < j \le k$.
Compute two quantities for the given tree:
The length $L$ of the longest jumping path where the labels of the vertices are nondecreasing. That is, $u_{a_ i} \le u_{a_ j}$ for all $1 \le i < j \le L$.
The number $M$ of jumping paths of length $L$ where the labels of the vertices are nondecreasing. Since this number may be large, give the remainder of $M$ when divided by the prime $11\, 092\, 019$.
The first line of input contains an integer $N$ denoting the number of vertices in the tree ($1 \leq N \leq 10^6$).
This is followed by $N$ lines of input indicating the labels $u_1$ through $u_ N$. Each label is an integer in the range $[0, 10^6]$.
The remaining $N-1$ lines describe the tree structure. Skipping the root (which has no parent) and starting with $i=2$, line $i$ gives the parent $p_ i < i$ of vertex $v_ i$.
Print a single line of output with two integers separated by a space. The first integer is $L$, and the second integer is $M$ modulo the prime $11\, 092\, 019$.
Sample Input 1 | Sample Output 1 |
---|---|
5 3 3 3 3 3 1 2 3 4 |
5 1 |
Sample Input 2 | Sample Output 2 |
---|---|
5 4 3 2 1 0 1 2 3 4 |
1 5 |
Sample Input 3 | Sample Output 3 |
---|---|
4 1 5 3 6 1 2 3 |
3 2 |
Sample Input 4 | Sample Output 4 |
---|---|
6 1 2 3 4 5 6 1 1 1 1 1 |
2 5 |