N. Colored Sticks
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ consisting of $$$n$$$ positive integers. For each $$$i$$$ such that $$$1 \le i \le n$$$, there are $$$a_i$$$ sticks of length $$$i$$$, and let $$$m$$$ be equal to the total number of sticks (i.e. $$$m = \displaystyle\sum_{i=1}^{n} a_i$$$).

You have $$$m$$$ colors, and for each stick, you must choose an integer $$$k$$$ such that $$$1 \le k \le m$$$, and color the $$$i$$$-th stick with the $$$k$$$-th color.

Your goal is to color these sticks in such a way that it would be impossible to form a square by choosing four sticks of the same color.

What is the minimum number of different colors you need to use?

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the size of the array.

The second line of the input consists of $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the number of sticks of each length.

Output

Output one line containing a single integer — the minimum number of distinct colors that are required.

Example
Input
3
4 1 1
Output
2
Note

In the first test case:

The total number of sticks is $$$4 + 1 + 1 = 6$$$.

It's possible to color the first $$$3$$$ sticks of length $$$1$$$ with the color $$$1$$$, and all other sticks with the color $$$2$$$.

It can be shown that it's not possible to color the sticks with only one color (since then it would be possible to form a square using sticks of length $$$1$$$).