/ 
Time Limit: 5 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます．
2^{A_l}+2^{A_{l+1}}+\dots+2^{A_r} が 2 べきとなるような整数の組 (l, r)\ (1\leq l\leq r\leq N) の個数を求めてください．ただし，2 べきとはある非負整数 k を用いて 2^k と表される数を言います．
制約
- 1\leq N\leq 2\times 10^5
- 0\leq A_i\leq 2\times 10^5
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる．
N A_1 A_2 \ldots A_N
出力
答えを出力せよ．
入力例 1
4 0 1 0 2
出力例 1
6
条件を満たす (l,r) は (1,1),(1,3),(1,4),(2,2),(3,3),(4,4) の 6 つです．
入力例 2
4 100 100 100 100
出力例 2
8
入力例 3
10 3 2 2 3 2 4 1 1 0 0
出力例 3
19
Score : 800 points
Problem Statement
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.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 2 \times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
4 0 1 0 2
Sample Output 1
6
The pairs (l, r) satisfying the condition are (1,1), (1,3), (1,4), (2,2), (3,3), (4,4), totaling six pairs.
Sample Input 2
4 100 100 100 100
Sample Output 2
8
Sample Input 3
10 3 2 2 3 2 4 1 1 0 0
Sample Output 3
19