A maze consists of $N$ rooms and $N$ one-way corridors. From the $i$-th room there is exactly one one-way corridor to the $k[i]$-th room.

An adventurer and a minotaur are in the maze. The adventurer will move from a room to the next room in one minute, while the minotaur will do the same in two minutes. The maze is constructed so that as long as the adventurer and the minotaur start moving at the same moment, they will eventually meet in the same room.

The adventurer and the minotaur choose two different rooms in the maze at the very beginning. After that, they will keep moving from one room to another room via the corridors. You are asked the maximum possible time for the adventurer and the minotaur to meet exactly in a room.

Input Specification

The first line contains an integer $N$, the number of rooms.

The second line contains $N$ numbers, of which the $i$-th number is $k[i]$.

• In $50\mathrm{\%}$ of the test cases, $1\le N\le 5000$;
• In $100\mathrm{\%}$ of the test cases, $1\le N\le 100000$.

Output Specification

The maximum possible time for the adventurer and the minotaur to meet in a room.

Sample Input 1

6
2 3 4 5 6 1

Sample Output 1

10

Sample Input 2

6
2 3 4 5 3 4

Sample Output 2

8

Explanation

In the second sample, if the adventurer starts at room $6$ and the minotaur starts at room $1$, they need $8$ minutes to meet at the same room (i.e., room $5$).