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 · sz_{uv}(u) + v · sz_{vu}(v), where 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 vth 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} ≠ −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.
Input
The first line of input contains an integer n: the size of the tree (2 ≤ n ≤ 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.
Output
Print the integer part of E.
Samples
input  output 

5
1 1 1 1 1
 67

5
1 1 1 1 1
 52

4
1 1 1 3
 42

4
1 1 2 2
 38

Problem Author: Alexey Danilyuk
Problem Source: Petrozavodsk Summer 2018. t.me/umnik_team Contest