问题描述

我们正在山脉中建立一个无线通信网络，通信站将设置在山峰的顶部。山峰位于一条直线上，且高度各不相同。为了最小化成本，网络结构需要呈现树状，即一个连接的图，且具有最少的边数。网络的结构（即每个通信站与哪些站相连）需要预先确定。

通信网络的构建方式如下：

1. 初始时，每个站点形成一棵仅包含该站点的树。
2. 每一步中，我们通过在两棵相邻的树之间建立一个连接来合并它们，连接的是两棵树中海拔最高的站点，因为所有山峰的高度都不同，这些站点是唯一确定的。这里，两棵树被称为相邻的，如果位于其中一棵树的一个山峰与另一棵树的山峰之间的所有山峰都属于这两棵树之一。
3. 重复步骤2，直到所有站点都被直接或间接地连接。

当某个站点检测到紧急事件时，警报消息将广播到所有站点。每个接收到消息的站点将消息转发给所有直接连接的站点，除了消息来源的那个站点。网络的直径（即从任意站点分发消息所需的跳数）取决于步骤2中选择连接的两棵树的方式。

为了估计最坏情况下的广播延迟，我们希望找到通过上述步骤构建的网络中可能的最大直径。

输入格式

输入包括单个测试用例，格式如下：

n  
h1  
h2  
...  
hn  

• 第一行包含一个整数 $n$ ，表示通信站的数量$( 3 \leq n \leq 10^6 )$。
• 接下来的 $n$ 行中，每行包含一个整数 $h_i$ 表示第 $i$ 个站点的高度$（ 1 \leq h_i \leq n ）$。所有站点的高度各不相同，即 $h_i \neq h_j$ 如果 $i \neq j$。

输出格式

输出一个整数，表示通过上述过程构建的网络可能的最大直径。

8
1
8
2
3
5
4
6
7

6

4
1
2
3
4

3