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 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 ≠ −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 ≤ n ≤ 10⁶).

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.