+ Time limit: 1 second + Memory limit: 256 megabytes ---------- In the ancient country of Codecup, there were $n$ cities numbered 1 to $n$. This country had $n-1$ bidirectional roads, and each road connected exactly two cities. We know that in ancient Codecup, there was a path from every city to every other city (in fact, the map of Codecup was structured as a [tree](https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%28%D9%86%D8%B8%D8%B1%DB%8C%D9%87_%DA%AF%D8%B1%D8%A7%D9%81%29)). A *path* is defined as a sequence of **distinct** cities, such as $v_1, v_2, \dots, v_k$, such that every two consecutive cities are connected by a road. The length of this path is $k$. The country's longest path refers to the path that has the greatest length among all possible paths. However, we have now lost the map of Codecup, and we only know, for each city, the number of roads emanating from it (its degree). Given these numbers, we want to consider a map among all possible maps for ancient Codecup such that the length of its longest path is maximized. We ask you to calculate this length. # Input The first line of input provides the number $n$, representing the total number of cities in ancient Codecup. $$2 \leq n \leq 1,000,000$$ The next line contains $n$ space-separated numbers $d_i$, where the $i$-th number, $d_i$, represents the number of roads connected to city $i$. $$1 \leq d_i \leq n - 1$$ It is guaranteed that based on the given sequence, at least one map for ancient Codecup can be constructed. # Output You must print the length of the longest path in the map of ancient Codecup on a single line. # Examples ## Sample Input 1 ``` 4 1 2 2 1 ``` ## Sample Output 1 ``` 4 ``` <details> <summary> **Explanation of Sample 1** </summary> ---------- The map of ancient Codecup can be structured as follows, such that the number of roads emanating from each city exactly matches the input values. Its longest path is $\langle 1, 2, 3, 4 \rangle$, which has a length of 4, and this is the maximum possible value.  ---------- </details> ## Sample Input 2 ``` 6 2 2 1 3 1 1 ``` ## Sample Output 2 ``` 5 ``` <details> <summary> **Explanation of Sample 2** </summary> ---------- One of its longest paths is $\langle 3, 1, 2, 4, 5 \rangle$, which has a length of 5. Among all other acceptable configurations for the map of ancient Codecup, this example yields the maximum length for the longest path.  ---------- </details>