Minimum Uncrowded Queue Length

In this problem, there are ( n ) students (numbered from (1) to (n)) who line up in order to register. They must stand in a line with increasing order of their numbers (i.e. student 1 is at the front). Each student ( i ) has a personal comfort distance ( a_i ). For student ( i ), if there exists another student whose distance from him/her is less than ( a_i ), a conflict occurs. The students want to form a queue with no conflicts. Your task is to determine the minimum possible total length of the queue (the distance from the first student to the last student) when the students maintain the order and avoid conflicts.

We denote the positions of students by ( p_1, p_2, \dots, p_n ) with ( p_1 \le p_2 \le \dots \le p_n ) (and you can assume ( p_1 = 0 )). For each student, the condition to avoid conflicts is:

• For student 1: ( p_2 - p_1 \ge a_1 ).
• For student ( n ): ( p_n - p_{n-1} \ge a_n ).
• For student ( i ) (( 2 \le i \le n-1 )): ( \min(p_i - p_{i-1}, p_{i+1} - p_i) \ge a_i ).

Observing that the minimal distance between two consecutive students ( d_i = p_{i+1} - p_i ) must satisfy for each adjacent pair:

( \begin{aligned} d_1 &\ge \max(a_1, a_2), \ d_i &\ge \max(a_i, a_{i+1]) \quad \text{for } 2 \le i \le n-1, \ d_{n-1} &\ge \max(a_{n-1}, a_n). \end{aligned} )

Thus, when ( n \ge 2 ), the minimum total length is:

[ \text{Length} = \sum_{i=1}^{n-1} \max(a_i, a_{i+1]). ]

If ( n = 1 ), there is only one student so the required length is ( 0 ).

inputFormat

The first line contains an integer ( n ) (the number of students). The second line contains ( n ) integers ( a_1, a_2, \dots, a_n ) where ( a_i ) denotes the personal distance requirement of the ( i)-th student.

outputFormat

Output a single integer which is the minimum total length of the queue such that no conflicts occur.

sample

1
100

0