大楼拆除

时间限制：2s
空间限制：1024MB

题目描述

有 $N$ 栋楼，第 $i$ 栋初始有 $A_i$ 层。一次操作可以选择正整数 $X$，使当前高度不少于 $X$ 的所有楼都降低一层；操作可进行任意多次。求所有可能最终景观的数量，对 $10^9+7$ 取模。两个景观只要有一栋楼的最终高度不同就视为不同。

输入格式

第一行一个整数 $N$，第二行 $N$ 个整数 $A_1,\ldots,A_N$。

输出格式

输出可能景观数对 $10^9+7$ 取模的结果。

样例输入 1

2
1 2

样例输出 1

4

样例输入 2

6
5 3 4 1 5 2

样例输出 2

32

数据范围

对于所有数据，$1\le N\le10^5$，$1\le A_i\le10^9$。