思路

这是一个典型的模拟题。我们需要按照题目描述的规则，一年一年地模拟山峰和山谷消失的过程，直到某一年不再有任何山消失为止。

核心模拟流程：

1. 数据结构：由于山会不断被移除，我们需要一个能够高效执行删除操作的数据结构。数组（如C++的 std::vector 或Java的 ArrayList）在删除中间元素时效率较低（时间复杂度为 $O(N)$），因为需要移动后续所有元素。相比之下，双向链表（如C++的 std::list 或Java的 LinkedList）是更理想的选择，因为它可以在 $O(1)$ 的时间内删除一个已知位置的元素。

2. 模拟循环：我们用一个变量 year 从 $1$ 开始计数，进入一个主循环。这个循环的终止条件是“某一年没有任何山消失”。

题目内容

Z 市以奇山秀林闻名世界。这里一共有 $n$ 座山排成一排，从左向右编号依次为 $1,2,…,n$ ，其中第 $i$ 座山的高度记为 $a_i$ ；

每座山的高度互不相同。如果第 $i(2≤i≤n-1)$ 座山的高度满足严格小于左右相邻的两座山，则第 $i$ 座山被称为山谷；

若满足严格大于左右相邻的两座山，则被称为山峰。由于神秘的地壳运动，每年山谷和山峰会轮流全部消失。若某一年所有山谷同时消失，下一年则是所有山峰同时消失。山的消失实际上是和相邻的山融为了一体，第 $i$ 座山消失后，第 $i-1$ 座山与第 $i+1$ 座山视为相邻(如果两座山均存在的话)。

假设今年是第一年，轮到山谷消失，小铭想知道第一次没有山消失是在第几年?

输入描述

输入第一行有一个正整数 $n(1≤n≤10^5)$ ，表示山的个数;

第二行有 $n$ 个正整数 $a_1,a_2,…,a_n(1≤a_i≤10^9)$，表示每座山的高度。

输出描述

输出一个正整数，表示第一个没有山消失的年份。

样例1

输入

6
5 7 1 2 8 3

输出

4

说明

第一年，山谷消失，第三座山是山谷，消失后数组变为 $[5$ $7$ $2$ $8$ $3$ ];

第二年，山峰消失，第二座山、第四座山是山峰，消失后数组变为 $[5$ $2$ $3$ ];

第三年，山谷消失，第二座山是山谷，消失后数组变为 $[5$ $3$]。

第四年，山峰消失，没有山峰，没有山消失。

注意，即使下一年有山谷消失，答案也应输出 $4$ ，第一个没有山消失的年份。