You are given a 0-indexed integer array units of length n, where units[i] is the number of units stored at position i.

First, choose one end of the array, position 0 or position n - 1, as the anchor. The choice is fixed for the whole process.

Then perform passes. Each pass starts at the anchor, extends to some target position, and removes at most one unit from every position it covers (anchor through target, inclusive) that still has units. The cost of a pass is the number of positions it covers (the 1-indexed distance from the anchor to the target).

Additionally, removing each single unit costs 1 (handling).

Return the minimum possible total cost, pass costs plus handling costs, to remove all units.

Examples

Example 1

Input: units = [1,2,3]
Output: 12
Explanation: Handling all 6 units costs 6. Anchor at position 2 (the right end) and make
three passes: one to position 0 (covers 3 positions, cost 3), one to position 1 (cost 2),
and one to position 2 alone (cost 1). Together they remove 1 unit from position 0, 2 from
position 1, and 3 from position 2, with pass cost 3 + 2 + 1 = 6. Total cost 6 + 6 = 12.