Cho một cây nhị phân hoàn chỉnh gồm $N$ nút, mỗi nút trên cây có một trọng số, theo thứ tự từ trên xuống dưới, từ trái sang phải lần lượt là $A_1,A_2, \cdots A_N$, như hình dưới đây:

Bây giờ Minh muốn cộng trọng số của các nút có cùng độ sâu lại với nhau, cậu ấy muốn biết tổng trọng số của các nút ở độ sâu nào là lớn nhất? Nếu có nhiều độ sâu có tổng trọng số cùng lớn nhất, hãy in ra độ sâu nhỏ nhất trong số đó.

Chú ý: độ sâu của nút gốc là $1$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$.

Dòng thứ hai chứa $N$ số nguyên $A_1,A_2, \cdots, A_N$.

Dữ liệu ra

In ra một số nguyên biểu thị đáp án.

Ví dụ

Input

7
1 6 5 4 3 2 1

Output

2

Ghi chú

Phạm vi dữ liệu

Với tất cả các test, $1 \le N \le 10^5$, $0 \le |A_i| \le 10^5$.

Nguồn: Lanqiao Cup 2019 vòng tỉnh, bảng A bài F (bảng B bài G).