给定一个高度为 $h_1, h_2, \cdots, h_N$ 的直方图。形式上，直方图被定义为如下点集： $$ \bigcup_{i=1}^N \{ (x, y) : i-1 \le x < i,\, 0 \le y < h_i \}. $$

你可以选择 $N$ 个整数 $x_1, x_2, \cdots, x_N$，满足 $1 \le x_i < h_i$，并减去一个高度为 $x_1, x_2, \cdots, x_N$ 的子直方图。移除该子直方图后，剩余的区域可以表示为： $$ \bigcup_{i=1}^N \{ (x, y) : i-1 \le x < i,\, x_i \le y < h_i \}. $$

下图展示了一个 $h_1 = 4$，$h_2 = 5$，$h_3 = 4$，$h_4 = 4$ 且 $x_1 = 1$，$x_2 = 2$，$x_3 = 3$，$x_4 = 2$ 的例子。

如果对于剩余区域中的任意一对点 $(p, q)$，都存在一条从 $p$ 到 $q$ 的曲线且该曲线完全位于剩余区域内部，则称剩余区域是连通的。

计算选择 $(x_1, x_2, \cdots, x_N)$ 使得剩余区域连通的方法数。

输入格式

第一行包含一个整数 $N$。 第二行包含 $N$ 个整数 $h_1, h_2, \cdots, h_N$。

数据范围

• $1 \le N \le 250,000$
• $2 \le h_i < 10^9$

子任务

子任务 1

$N \le 3$，且对于所有 $i = 1, 2, \cdots, N$ 满足 $h_i \le 100$

子任务 2

$N \le 3$

子任务 3

$h_1 = h_2 = \cdots = h_N$

子任务 4

$h_1 \le h_2 \le \cdots \le h_N$

子任务 5

无附加限制。

输出格式

输出选择 $(x_1, x_2, \cdots, x_N)$ 使得剩余区域连通的可能方法数，模 $10^9 + 7$ 的结果。