题目描述

小帅还是高估了自己的种植技术，插杆种植以失败告终，但小帅发现了水培种植的新大陆，水培种植就是把植物的根部泡在水里面，这样植物就可以存活，听起来水培种植很简单。

于是小帅去花卉市场购买了 n 棵水培树，回到家后排成一排并给每棵树按照从左往右的顺序编上编号 1，2，3……，经过数天后，水培树看起来并没有长得很好，小帅感觉没有太多时间和精力去照顾那么多盆水培树，于是决定从 n 盆水培树中选择一棵具备以下条件来精心照顾，其他的交给妈妈帮忙打理：

1. 这棵树的高度大于左右两棵树的高度
2. 这棵树的高度是在满足条件1的所有树中是最大的

测试数据保证一定有答案，且第一棵树和最后一棵树一定都不满足条件。

输入格式

第一行输入一个数字 n，表示水培树的数量。

第二行输入 n 个数字，表示每棵水培树的高度 h_i。

输出格式

输出一个数字表示答案。

输入输出样例

输入样例 #1：

10
1 3 2 4 3 6 7 9 8 1

输出样例 #1：

9

样例解释 #1：
满足条件1的高度有：3 4 9，最大的是9。

输入样例 #2：

5
1 3 2 4 3

输出样例 #2：

4

样例解释 #2：
满足条件1的高度有：3、4，最大的是4。

数据范围

对于 100% 的数据保证：
1 <= n <= 1000000，1 <= h_i <= 1000000000