Minimum Cost to Convince the Readers

Rebecca’s landscape photo must convince her readers that the mountain in it is real. We represent the photo as a sequence of N columns. In the i-th column, the bottom h_i pixels form the mountain. The readers are convinced if the photo contains a mountain peak – that is, there exists an index p (1 ≤ p ≤ N) such that

[ h_{1} \le h_{2} \le \cdots \le h_{p} \ge \cdots \ge h_{N} ]

Rebecca can edit the photo by sending an email with three integers (i, j, k) satisfying

[ 1 \le i < j < k \le N, \quad h_{i} > h_{j} \quad \text{and} \quad h_{k} > h_{j}. ]

The editor will add one extra mountain pixel to column j (i.e. increase h_j by 1) and charge a fee of

[ h_{i} + h_{j} + h_{k}. ]

Note that the increase in h_j may affect the fee of future edits. Help Rebecca find the minimum total cost necessary so that, after a sequence of edits, the photo becomes unimodal (contains a mountain peak). If it is impossible to achieve a unimodal photo, output -1.

inputFormat

The first line contains an integer N (3 ≤ N ≤ 8), representing the number of columns. The second line contains N integers h₁, h₂, ..., h_N (1 ≤ h_i ≤ 10), describing the initial number of mountain pixels in each column.

Note: N and the heights are small to allow a state-space search.

outputFormat

Output a single integer—the minimum total cost required to edit the photo so that it contains a mountain peak. If it is impossible, output -1.

sample

3
1 2 3

0