Chia dãy

Cho dãy số $A$ gồm $n$ số nguyên $a_1, a_2, \dots, 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 thỏa 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?

Trong tệp văn bản CHIADAY.INP gồm:

• 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, \dots, a_n$ $(0 \le a_i \le 2 \times 10^4; 1 \le i \le n)$;

Đưa ra tệp văn bản CHIADAY.OUT một số nguyên là số đoạn ít nhất chia được. Nếu không chia được thì in ra -1.

• 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 \le 3$;
• Subtask 3: 25% số test có $n \le 5000$;
• Subtask 4: 25% số test không có ràng buộc gì thêm.