Converging Maze: Largest Sum Cycle

Each cell numbered 0..N−1 has at most one one-way exit edge[i]; edge[i]=−1 means it has no exit. Output the maximum sum of node numbers over all directed cycles; output −1 if there is no cycle.

输入格式

The first line contains N (1..200000), and the second line contains N integers, each either −1 or in [0,N−1].

输出格式

Output the maximum sum of node numbers in a cycle, or −1.

样例 1

输入：

23
4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21

输出：

45

样例 2

输入：

1
-1

输出：

-1

样例 3

输入：

4
1 0 3 2

输出：

5