시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1 1 1 100.000%

문제

Consider a labeled tree with its vertices numbered from $1$ to $n$.

Let us define the weight of the tree as the sum over all edges $uv$ of values $u \cdot \mathrm{sz}_{uv}(u) + v \cdot \mathrm{sz}_{vu}(v)$, where $\mathrm{sz}_{vu}(v)$ is the size of subtree containing $v$ after deleting edge $(vu)$.

You are given an array $a$ of size $n$. Elements of the array are either integers between $1$ and $n-1$ (inclusive), or equal to $-1$. The $v$-th element corresponds to the degree of vertex $v$. We say that a tree with $n$ vertices is good if for all $v$ such that $a_{v} \ne -1$, it is true that the degree of $v$ equals to $a_{v}$. In other words, if $a_{v} = -1$, then $v$ can have any degree, and otherwise, its degree is fixed and equal to $a_{v}$.

Let us choose one of the good trees randomly with equal probability. Denote the expected value of the weight of this tree as $E$. Find the integer part of $E$.

입력

The first line of input contains an integer $n$: the size of the tree ($2 \le n \le 10^{6}$).

The second line of input contains an array of size $n$. Each element of the array is either an integer between $1$ and $n-1$ (fixed degree), or equal to $-1$ (arbitrary degree). It is guaranteed that the sum of absolute values of elements is not greater than $2n-2$.

출력

Print the integer part of $E$.

예제 입력 1

5
1 -1 -1 -1 -1

예제 출력 1

67

예제 입력 2

5
-1 -1 -1 -1 1

예제 출력 2

52

예제 입력 3

4
1 1 1 3

예제 출력 3

42

예제 입력 4

4
1 1 2 2

예제 출력 4

38