ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Petrozavodsk Summer 2018. t.me/umnik_team Contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Tree Average Weight

Time limit: 2.0 second
Memory limit: 64 MB
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 · szuv(u) + v · szvu(v), where szvu(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 av ≠ −1, it is true that the degree of v equals to av. In other words, if av = −1, then v can have any degree, and otherwise, its degree is fixed and equal to av.
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 ≤ 106).
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

inputoutput
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
To submit the solution for this problem go to the Problem set: 2120. Tree Average Weight