考虑一棵顶点编号从 $1$ 到 $n$ 的带标号树。

定义树的权值为所有边 $uv$ 的值之和，即 $\sum_{uv} (u \cdot \text{sz}_{uv}(u) + v \cdot \text{sz}_{vu}(v))$，其中 $\text{sz}_{vu}(v)$ 表示删除边 $(vu)$ 后包含 $v$ 的子树大小。

给定一个大小为 $n$ 的数组 $a$。数组元素要么是 $1$ 到 $n-1$ 之间的整数（包含边界），要么等于 $-1$。第 $v$ 个元素对应顶点 $v$ 的度数。如果对于所有满足 $a_v \neq -1$ 的 $v$，树中顶点 $v$ 的度数都等于 $a_v$，则称这棵 $n$ 个顶点的树是“好的”。换句话说，如果 $a_v = -1$，则 $v$ 可以有任意度数；否则，其度数固定为 $a_v$。

假设我们等概率地随机选择一棵“好的”树。记该树权值的期望值为 $E$。求 $E$ 的整数部分。

输入格式

第一行包含一个整数 $n$：树的大小（$2 \le n \le 10^6$）。

第二行包含一个大小为 $n$ 的数组。每个元素要么是 $1$ 到 $n-1$ 之间的整数（固定度数），要么等于 $-1$（任意度数）。保证所有元素的绝对值之和不超过 $2n - 2$。

输出格式

输出 $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