我们正在山脉中建立一个无线通信网络。通信基站位于山峰上。这些山峰位于一条直线上，且海拔各不相同。

为了最小化成本，我们的通信网络应具有树状结构，即边数最少的连通图。网络的结构，即哪些基站与哪些其他基站通信，应提前决定。

我们按如下方式构建通信网络：

1. 最初，每个基站各自形成一棵仅包含该基站的树。
2. 在每一步中，我们通过在不同树中的两个基站之间建立连接，合并两棵相邻的树。当一棵树中的某个山峰与另一棵树中的某个山峰之间的所有山峰都属于这两棵树时，称这两棵树是相邻的。用于连接的基站是两棵树中海拔最高的山峰所在的基站；由于山峰海拔各不相同，这些基站是唯一确定的。
3. 重复步骤 2，直到所有基站直接或间接地连通。

图 D.1 展示了样例 1 中树形成过程的一个示例。

图 D.1. 样例 1 的树形成过程

当某个基站检测到紧急事件时，警报消息应广播给所有基站。在接收到消息时，每个基站会将消息转发给所有与其有直接连接的基站，但消息来源的基站除外。网络的直径，即从任意基站发起消息分发所需的跳数，取决于上述步骤 2 中对两棵树的选择。

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

输入格式

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

$n$ $h_1$ $\vdots$ $h_n$

其中，$n$ 是通信基站的数量（$3 \le n \le 10^6$），$h_i$ 是表示第 $i$ 个基站海拔的整数（$1 \le h_i \le n$）。基站的海拔各不相同，即当 $i \neq j$ 时，$h_i \neq h_j$。

输出格式

输出一行，包含一个整数，表示该树可能的最大直径。

样例

样例输入 1

8
1
8
2
3
5
4
6
7

样例输出 1

6

样例输入 2

4
1
2
3
4

样例输出 2

3