AT_arc216_c [ARC216C] Count Power of 2

You are given a sequence of non-negative integers $ A = (A_1, A_2, \ldots, A_N) $ of length $ N $ . Find the number of pairs of integers $ (l, r)\ (1 \leq l \leq r \leq N) $ such that $ 2^{A_l} + 2^{A_{l+1}} + \dots + 2^{A_r} $ is a power of $ 2 $ . Here, a power of $ 2 $ is a number expressible as $ 2^k $ for some non-negative integer $ k $ .

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Print the answer.

### Sample Explanation 1 The pairs $ (l, r) $ satisfying the condition are $ (1,1), (1,3), (1,4), (2,2), (3,3), (4,4) $ , totaling six pairs. ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 0 \leq A_i \leq 2 \times 10^5 $ - All input values are integers.