Cho dãy số A gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\), có thể chia dãy số này thành các đoạn liên tiếp sao cho tổng các số trong mỗi đoạn là lũy thừa cơ số 2.

Ví dụ: dãy gồm 6 số \(A = \{5, 3, 1, 1, 1, 3\}\) có 2 cách chia thoả mãn:

• Cách 1: Chia 3 đoạn \(\{5,3\};\{1,1\};\{1,3\}\) có tổng lần lượt là \(8=2^3; 2=2^1; 4=2^2\).
• Cách 2: Chia 4 đoạn \(\{5,3\};\{1\};\{1\};\{1,3\}\) có tổng lần lượt là \(8=2^3; 1=2^0; 1=2^0; 4=2^2\).

Yêu cầu: Em hãy viết chương trình tìm cách chia dãy A trên thành các đoạn con liên tiếp sao cho số lượng đoạn con là ít nhất và tổng các số trong mỗi đoạn là lũy thừa cơ số 2?

Input

• Dòng 1 là số nguyên dương \(n\) \((1 \leq n \leq 10^5)\);
• Dòng 2 gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((0 \leq a_i \leq 2 \times 10^4; 1 \leq i \leq n)\).

Output

• Đưa ra một số nguyên là số đoạn ít nhất chia được. Nếu không chia được thì in ra -1.

Example

6
5 3 1 1 1 3

3

Ràng buộc

• Subtask 1: \(25\%\) số test có tổng tất cả các số trong dãy A là một lũy thừa cơ số 2.
• Subtask 2: \(25\%\) số test có \(n \leq 3\).
• Subtask 3: \(25\%\) số test có \(n \leq 5000\).
• Subtask 4: \(25\%\) số test không có ràng buộc gì thêm.