题目描述

对于一个长度为 $n$ 的正整数数列 $a$，Farmer John 定义 M 函数 $M(l, r)$ 如下：

$\max \limits _ {l \leq i \leq r}{a _ i}$ 代表 $a _ l, a _ {l + 1}, \cdots, a _ {r - 1}, a _ r$ 中的最大值。

$\left \lfloor x \right \rfloor$ 代表 $\leq x$ 的最大整数。比如 $\left \lfloor 4.2 \right \rfloor = 4$，$\left \lfloor 5 \right \rfloor = 5$。

$\max(x, y)$ 代表 $x, y$ 中的最大值。

现在给定 $n$ 和 $a$，请你求出 $M(1, n)$。

输入格式

输入共两行。

第一行为一个整数 $n$。

第二行为 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$，对应题目中的正整数数列 $a$。

输出格式

输出共一行一个整数，代表 $M(1, n)$ 的值。

10
3 72 26 91 5 84 18 29 50 23

11

提示

样例 1 解释

我们这里暂时使用 $\max \{a _ l, a _ {l + 1}, \cdots, a _ r\}$ 来表示 $a _ l, a _ {l + 1}, \cdots, a _ r$ 中的最大值。

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq n \leq 5 \times 10 ^ 5$，$1 \leq a _ i \leq 10 ^ 9$。