The entrance to CB is blocked with snow! The snow can be represented as an array of \(N\) integers, where the \(i\)-th integer is the amount of snow in the \(i\)-th area (\(1 \le i \le N\)).

You are tasked with moving the snow.

It takes exactly \(1\) minute for you to move \(1\) unit of snow from one area to the one of the neighbouring areas.

Formally, moving \(1\) unit of snow from the \(i\)-th area (\(1 \le i \le N\)) to the \(i-1\)-th area or to the \(i+1\)-th area takes 1 minute.

Your goal is to move all the snow so that each unit of snow is either located in the \(0\)-th area or the \(N+1\)-th area.

Constraints

\(1 \le N \le 10^5\)

\(1 \le A_i \le 10^9\)

Input Specification

The first line contains an integers \(N\), which is the number of areas.

The next line contains \(N\) space-separated integers, \(A_i\), the amount of snow in the \(i\)-th area.

Output Specification

Output the minimum amount of time needed to time to move all the snow.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

24