Description

Given a complete binary tree with $N$ nodes, each node has a weight. In the order from top to bottom and from left to right, the weights are $A_1, A_2, \cdots, A_N$, as shown in the figure below:

Now Xiaoming wants to add up the weights of nodes at the same depth. He wants to know at which depth the sum of node weights is the largest. If there are multiple depths whose sums are tied for the largest, output the smallest such depth.

Note: The depth of the root is $1$.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $A_1, A_2, \cdots, A_N$.

Output Format

Output one integer representing the answer.

7
1 6 5 4 3 2 1

2

Hint

For all testdata, $1 \le N \le 10^5$, and $0 \le |A_i| \le 10^5$.

Lanqiao Cup 2019 NOI Qualifier, Group A Problem F (Group B Problem G).

Translated by ChatGPT 5