2048 P81018


Statement
 

pdf   zip

html

This problem is somehow inspired by the well known 2048 game. Here, you are given a collection of natural numbers between 1 and 2048. The only allowed operation is to pick any two equal numbers, remove them from the collection, and add their sum to the collection. You win if you manage to get exactly the number 2048 after zero or more operations.

Given a sequence of n numbers, consider all the subsequences of consecutive numbers in it. How many of them have a collection of numbers for which you can win?

Input

Input consists of several cases, each one with n followed by n natural numbers between 1 and 2048. Assume 1 ≤ n ≤ 104.

Output

For every case, print the number of winnable subsequences.

Public test cases

  • Input

    1  2048
2  2000 2000
7  2048 512 42 1024 512 23 1024

    Output

    1
0
12
    • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++