24960번 - Wireless Communication Network 다국어

문제

We are setting up a wireless communication network in a mountain range. Communication stations are to be located on the summits. The summits are on a straight line and have different altitudes.

To minimize the cost, our communication network should have a tree structure, which is a connected graph with the least number of edges. The structure of the network, that is, which stations to communicate with which other stations, should be decided in advance.

We construct the communication network as follows.

1. Initially, each station forms a tree consisting of only that station.
2. In each step, we merge two trees that are adjacent by making a link between two stations in different trees. Two trees are called adjacent when all the summits in between a summit in one tree and a summit in the other belong to one of these two trees. Stations to link are those on the highest summits of the two trees; they are uniquely determined because the altitudes of the summits are distinct.
3. Repeat the step 2 until all the stations are connected, directly or indirectly.

Figure D.1 depicts an example of the tree formation for Sample 1.

When a station detects an emergency event, an alert message should be broadcast to all the stations. On receiving a message, each station relays the message to all the stations with direct links, except for one from which it has come. The diameter of the network, that is, how many hops are sufficient to distribute messages initiated at any stations, depends on the choice of the two trees in the step 2 above.

To estimate the worst case delay of broadcast, we want to find the largest diameter of the network possibly constructed by the above procedure.

Figure D.1. The tree formation for Sample 1

입력

The input consists of a single test case of the following format.

$\begin{align*}& n \\ & h_1 \\ & \vdots \\ & h_n \end{align*}$

Here, $n$ is the number of communication stations (3ドル ≤ n ≤ 10^6$), and $h_i$ is an integer representing the altitude of the $i$-th station (1ドル ≤ h_i ≤ n$). The altitudes of the stations are distinct, that is, $h_i \ne h_j$ if $i \ne j$.

출력

Output in a line a single integer representing the largest possible diameter of the tree.

제한

힌트