Cho dãy số ~A~ gồm ~n~ số nguyên ~a_1, a_2, ..., 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 \le n \le 10^5~);
• Dòng 2 gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~0 \le a_i \le 2 \times 10^4~; ~1 \le i \le n~).

Output

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

Sample Input 1

6
5 3 1 1 1 3

Sample Output 1

3

Subtasks