C. Water Remaining
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You made a wooden water tank. When viewed from directly above, the tank is rectangular. The upper edge is at the same height throughout the tank. However, the bottom may not be flat – it could be stepped. Along the length of the tank, the bottom is divided into sections of equal length. Within each section, the bottom is flat and level. The depth may vary from section to section.

The tank was filled with water up to its upper edge. Later, the boards at both ends came off, and water spilled out of the tank. Even so, some water may still remain in the deeper parts of the tank. Calculate the total amount of water remaining. Here, the amount of water kept in one section per unit depth is defined as 1.

Figure C.1 shows the states of the tank. From left to right, they represent the empty state, the fully filled state, and the state in which the boards at both ends have come off, respectively.

Figure C.1: The tank

In the first test case of Sample Input 1, there are 5 sections whose depths are $$$3$$$, $$$8$$$, $$$7$$$, $$$4,$$$ and $$$6$$$ respectively. Figure C.2 shows cross-sectional views of this tank. The left figure shows the fully filled state, and the right figure shows the state in which the boards at both ends have come off. The two consecutive sections, the 2nd and 3rd, are deeper than their adjacent sections, so some water remains there, and its surface is at the same height as the bottom of the 4th section. $$$8-4=4$$$ of water remains in the 2nd section, and $$$7-4=3$$$ of water remains in the 3rd section. No water remains in other sections. Thus, the total amount of water remaining is $$$4+3=7$$$.

Figure C.2: The cross-sectional views of the first test case of Sample Input 1
Input

The input contains one or more test cases, each in the following format.

$$$n$$$
$$$d_{1}$$$ $$$d_{2}$$$ $$$\cdots$$$ $$$d_{n}$$$

A test case consists of two lines. In the first line, the number of sections $$$n$$$ is given ($$$1 \leq n \leq 100$$$). For each $$$k = 1,2,\ldots,n$$$, the integer $$$d_k$$$ denotes the depth, measured from the upper edge, of the $$$k$$$-th section from one end ($$$1 \leq d_k \leq 1000$$$).

The end of the input is indicated by a line containing a zero. The number of test cases does not exceed 100.

Output

For each test case, output in a line the total amount of water that remains.

Example
Input
5
3 8 7 4 6
9
11 15 14 1 7 5 11 4 9
6
4 6 6 6 4 3
6
5 9 7 8 9 4
1
300
2
300 400
0
Output
7
18
6
13
0
0