Problem Description

Given the input $A_0...A_{N−1}$, we want to find an array $H_0...H_{M−1}$ that satisfies the following conditions and output its length $M$:
- All $H_i$ are non-negative integers.
- All elements in the array are distinct. That is, if $i\neq j$, then $H_i\neq H_j$.
- The array represents a binary heap. That is, $H_i < H_{2i+1}$ and $H_i < H_{2i+2}$ always hold.
- $A$ is a suffix of $H$. That is, for all $0\leq k<N$, $A_k = H_{M−N+k}$.

If there are multiple possibilities, output the smallest $M$. If no such $H$ exists, output $-1$.

Input Format

The input is given in the following format:

$N$ $A_0$ $A_1\cdots A_{N-1}$

Output Format

Output the solution to the problem in one line.

Sample Input and Output

Sample Input #1

3
4 2 3

Sample Output #1

5

Sample Input #2

3
3 1 2

Sample Output #2

-1

Sample Input #3

4
10 20 40 30

Sample Output #3

4

Sample Input #4

4
9 2 3 6

Sample Output #4

8

Notes/Hints

Each variable in the input satisfies the following constraints:
- $1\leq N\leq 100$
- $0 \leq A_{i} \leq 10^9$
- $A_i$ are distinct non-negative integers

见题面 Input 部分

见题面 Output 部分