The best selling vegetable in Byteland is logarithmic paprika. As the name of this great vegetable suggests, the weight of each paprika is the power of 2 grams. The lightest paprika weighs $2^{0}$ grams, while the largest one weighs $2^{k}$ grams.

Residents of Byteland don't like buying pieces of paprika and so salesmen are forced to sell only whole paprika. What is more, bytean people are very exact and they do not tolerate situations when salesman is not able to sell the exact weight of paprika they are willing to buy. This causes stress among all salesmen of Byteland - some cases of insomnia have been observed as well. One of your friends, who owns vegetable garden, asked you to write a program which is supposed to help salesmen.

Write a program which:

• reads a description of the current stock of paprika from the standard input,
• determines the smallest weight of a paprika that cannot be weighed without cutting any paprika,
• writes the result to the standard output.

Input Format

The first line of the input contains one integer $ k $ ($1 ≤ k ≤ 10$), meaning that weights of available paprika are from the set $2^0, 2^1, \ldots, 2^k$. Second line contains $ k + 1$ positive integers $ p_{0}, p_{1}, \ldots, p_{k} $ not greater than 1 000, separated with single spaces and representing the current stock: $ p_{0}$ paprika of weight 1 gram, $ p_{1}$ - of weight 2 grams, ..., $p_{k}$ - of weight $2^{k} $ grams.

Output Format

The first and only line of the output should contain one positive integer $ x $ - the smallest weight that cannot be weighed without cutting any paprika.

Example

Input

2
2 1 1

Output

9

Notes

All weights from 1 to 8 can be weighed using paprika on the stock: 1 = 1, 2 = 1 + 1, 3 = 1 + 2, 4 = 4, 5 = 1 + 4, 6 = 1 + 1 + 4, 7 = 1 + 2 + 4, 8 = 1 + 1 + 2 + 4. Value 9 can not be weighed, therefore it is the answer to the example.