给定 $n$ 个非负整数表示每个宽度为 $1$ 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由高度为 $0,1,0,2,1,0,1,3,2,1,2,1$ 表示的高度图，在这种情况下，可以接 $6$ 个单位的雨水(黑色为柱子，蓝色为水）。

输入格式

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

第二行$n$个整数$a_1,a_2,\dots,a_n$表示每个柱子的高度，每个柱子高度不超过$10^4$。

输出格式

一行一个整数，表示能接到多少单位的雨水。由于这个数可能会很大，所以我们只需要知道$mod \quad 10007 \quad$的结果。

样例

样例输入

12
0 1 0 2 1 0 1 3 2 1 2 1

样例输出

6

数据范围与提示

• 对于 $100 \\%$ 的数据，$1 \leq n \leq 10^6$。
• 时间限制：$1\mathrm{s}$
• 空间限制：$256\mathrm{MB}$