该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

输入格式

第一行一个正整数 n$。

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

输出格式

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

样例 1 输入

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

样例 1 输出

6

数据范围

对于 $100\%$ 的数据满足： $1 ≤ n ≤ 10^6$。