Jumping Path

Time limit10sMemory limit512 MB

Summary

Given a rooted tree with labels, find the length of the longest ancestor chain with nondecreasing labels, and count how many such chains of that length exist modulo 11092019.

Level: Hard8 of 10
Topics: Dynamic programming, DFS, Tree, Sorting
Solved: No attempts yet

Problem

You are given a rooted tree where each vertex has a non-negative integer label.

A jumping path is a sequence of vertices v1, v2, ..., vk where vi is an ancestor of vj for all i < j. Here vi is an ancestor of v**i+1, but not necessarily the parent of v**i+1, which is where the jumping in the name comes from.

Compute two quantities:

The length (number of vertices) of the longest jumping path whose vertex labels are nondecreasing.
The number of jumping paths of that length whose vertex labels are nondecreasing.

Input

The first line contains an integer n (1 ≤ n ≤ 106), the number of vertices in the tree. Vertices are numbered from 1 to n, and vertex 1 is the root.

Each of the next n lines contains an integer x (0 ≤ x ≤ 106), the labels of the vertices, in vertex order.

Each of the next n − 1 lines contains an integer p (1 ≤ p ≤ *n), the parents of vertices 2 through n, in vertex order.

The vertices are guaranteed to form a single tree: connected and acyclic.

Output

Output a single line with two integers separated by a space.

The first integer is the length of the longest jumping path whose labels are nondecreasing. The second integer is the number of jumping paths of that length whose labels are nondecreasing. The second integer may be large, so output it modulo 11092019.

Examples4

Example 1
Input
```
5
3
3
3
3
3
1
2
3
4
```
Expected output
```
5 1
```
Example 2
Input
```
5
4
3
2
1
0
1
2
3
4
```
Expected output
```
1 5
```
Example 3
Input
```
4
1
5
3
6
1
2
3
```
Expected output
```
3 2
```
Example 4
Input
```
6
1
2
3
4
5
6
1
1
1
1
1
```
Expected output
```
2 5
```