Maximizing Monkey Happiness

In the world of OI, the legendary HuCe has received a magical tree from a mysterious man called Little O. This tree is a rooted tree with n nodes labeled from 1 to n, with node 1 as the root. Each node i has a weight a_i. The weights form a permutation of the set \(\{0,1,\dots,n-1\}\) with \(a_1 = 0\). HuCe plans to raise n monkeys, one initially placed at each node.

Every second, each monkey at node i attempts to jump to its parent with probability

[ p(i)=\begin{cases} 0 & \text{if } i = 1,\ \frac{(a_i+x)\bmod n}{n} & \text{if } 2 \le i \le n, \end{cases} ]

where x is a nonnegative integer representing the grams of "Golden Fertilizer" added to the tree. If the jump is unsuccessful (which happens with probability \(1-p(i)\)), the monkey will randomly and uniformly move to one of the nodes in the subtree of node i (including node i itself).

At the \(i\)th second, HuCe records \(g_i\), the fraction of monkeys that successfully jumped to their parent nodes. The long-term average happiness index is taken as the average of \(g_0, g_1, \dots, g_T\) over a huge number of seconds \(T = (n+1)^{99999^{99999^{99999}}}\).

Before the process begins, HuCe can add \(x\) grams of fertilizer to the tree. The addition changes each node's weight to:

[ (a_i + x) \bmod n. ]

Since the mapping \(a \to (a+x) \bmod n\) is a bijection on \(\{0,1,\dots,n-1\}\), the set of weights across all nodes becomes a permutation of \(\{0,1,\dots,n-1\}\). In particular, the sum of the weights over all nodes is constant:

[ \sum_{i=1}^{n} (a_i+x)\bmod n = \sum_{r=0}^{n-1} r = \frac{n(n-1)}{2}. ]

However, note that the monkey at the root (node 1) never attempts a jump (since \(p(1)=0\)). Therefore, the total contribution to the expected happiness index comes only from nodes 2 to n. The overall expected happiness index can be expressed as:

[ \text{Expected Happiness} = \frac{1}{n^2} \left(\frac{n(n-1)}{2} - \big((0+x) \bmod n\big)\right). ]

To maximize the expected happiness index, we need to minimize \((x \bmod n)\). The minimum possible value for \(x \bmod n\) is 0. Thus, any nonnegative integer \(x\) satisfying:

[ x \equiv 0 \pmod{n} ]

will maximize the happiness index. The simplest choice is \(x = 0\).

Your task is to determine the optimal amount of fertilizer (in grams) to add to the tree to maximize the monkeys' happiness index. If there are multiple optimal answers, output the smallest nonnegative integer which is 0.

inputFormat

The input begins with a line containing a single integer n (the number of nodes).

The next line contains n space-separated integers representing the weights \(a_1, a_2, \dots, a_n\) which form a permutation of \(\{0,1,\dots,n-1\}\) (with \(a_1 = 0\)).

The following n-1 lines each contain one integer. For i from 2 to n, the i-1th line gives the parent \(p_i\) of node i (each \(p_i\) is an integer between 1 and n).

outputFormat

Output a single integer: the optimal amount of fertilizer (in grams) to add to the tree to maximize the expected happiness index. If there are multiple answers, output the smallest one.

sample

3
0 1 2
1
1

0