Maximum Historical Income

The price on day i is A[i]. You initially hold 1 unit of the asset and can hold at most 1 unit at any time; you may sell on any day and buy when you are not holding. Find the maximum total profit and output it modulo 10^9.

输入格式

The first line contains n; the second line contains n prices. 1≤n≤200000, 0≤A[i]≤10^9.

输出格式

Output the maximum total profit mod 1000000000.

样例 1

输入：

7
1 2 3 3 2 1 5

输出：

7

样例 2

输入：

3
5 1 1

输出：

5

样例 3

输入：

4
0 1000000000 0 1000000000

输出：

0