题目描述

风光奇秀的张家界国家森林公园以其独特的石柱地貌著称。在一座座高耸入云的山柱间攀登，宛如行游在一幅绝美的东方山水画中。

你可以把全部 $n$ 座山峰看作一条直线排列，每座山峰的横向间距都为 $1$，第 $i$ 座山峰的高度为 $h_i$。现在需要在第 $1$ 座山峰和第 $n$ 座山峰之间搭建一条直线索道，游客可以乘坐缆车沿着这条索道俯瞰风景。由于缆车会经过每一座山峰，所以需要保证索道在任何一处的高度不能低于此处山峰的高度。索道起点的高度即为第一座山峰的高度；终点处设有垂直升降机，因此无需担心索道在终点处的位置过高。

建设索道的费用取决于索道在终点处的高度，因此你需要保证索道在终点处的高度尽可能小。请输出这个最小高度。

输入格式

第一行：一个整数 $n$，表示山峰数量；

第二行：$n$ 个整数，分别表示每座山峰的高度。

输出格式

一个整数，表示索道在终点处的最小高度。

样例

5
3 4 9 2 3

15

4
8 7 6 2

5

样例 $2$ 解释

共 $4$ 座山峰，高度分别为 $8,7,6,2$。那么索道在每一座山峰处的高度为 $8,7,6,5$。

数据规模与约束

对于 $40\%$ 的数据，$2≤n≤10，1≤h_i≤100$。

对于 $100\%$ 的数据，$2≤n≤10^6，1≤h_i≤10^9$。