假设给定一个高度为 $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$。

输出格式

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

数据范围

• $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

• 无附加限制。