#3331. 接水

接水

Description

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

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

Format

Input

第一行一个正整数 n。 第二行 n 个整数 a1 , a2 , . . . , an 表示每个柱子的高度,每个柱子高度不超过 10^4。

Output

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

Samples

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

Limitation

对于 100% 的数据满足: 1 ≤ n ≤ 1e6