Take a sufficiently large integer \(P\) and precompute the prefix sums of \(2^{A_i}\) modulo \(P\). We prepare a way to quickly determine, for each \((l, k)\), whether there exists an \(r\) such that \(2^{A_l} + \ldots + 2^{A_r} \equiv 2^k \pmod{P}\) using an associative array.

When \(2^{A_l} + \ldots + 2^{A_r}\) is a power of \(2\), letting \(M = \max(A_l, \ldots, A_r)\), the value must be one of \(2^M, 2^{M+1}, \ldots, 2^{M + \lfloor \log_2 N \rfloor}\).

We find the number of pairs \((l, r)\) satisfying the condition using divide and conquer. For an interval \([L:R]\), we pick some \(m\) satisfying \(A_m = \max(A_L, \ldots, A_R)\), and count the pairs \((l, r)\) with \(L \leq l \leq m \leq r \leq R\) that satisfy the condition.

If \(m - L \leq R - m\), for each \(l = L, \ldots, m\) and \(k = A_m, A_m + 1, \ldots, A_m + \lfloor \log_2 N \rfloor\), we check whether there exists an \(r\ (m \leq r \leq R)\) satisfying \(2^{A_l} + \ldots + 2^{A_r} = 2^k\). If \(m - L > R - m\), we instead iterate over \(r\) to check.

The time complexity is expected \(O(N \log^2 N)\). An \(O(N \log^3 N)\) solution with a sufficiently small constant factor may also pass.

---

Probability Analysis

Let \(P\) be a random prime with \(2^{56} \leq P < 2^{63}\).

Lemma. For integers \(a, b\ (a \neq b)\) with \(0 \leq a, b < 2^{200018}\), the probability that \(a \equiv b \pmod{P}\) is at most approximately \(1.67 \times 10^{-14}\).

(Proof) Let \(p_1, p_2, \ldots\) be the primes not less than \(2^{56}\) in ascending order. The smallest \(k\) such that \(p_1 p_2 \cdots p_k > 2^{200018}\) is \(k = 3562\). By the prime number theorem, the number of primes in \([2^{56}, 2^{63})\) is estimated to be approximately \(2.14 \times 10^{17}\), so the probability that \(a \equiv b\) is at most \(\dfrac{3561}{2.14 \times 10^{17}} \approx 1.67 \times 10^{-14}\). (End of proof)

To output the correct answer, the following condition must hold:

• For all triples \((l, r, k)\) with \(1 \le l \le r \le N\) and \(M \le k \le M + \log_2 N\), if \(2^{A_l} + 2^{A_{l+1}} + \dots + 2^{A_r} \ne 2^k\), then \(2^{A_l} + 2^{A_{l+1}} + \dots + 2^{A_r} \not\equiv 2^k \pmod{P}\).

The probability that all triples \((l, r, k)\) satisfy this is at least \(1 - 1.67 \times 10^{-14} \times \frac{N(N+1)}{2}(\lfloor \log_2 N \rfloor + 1)\), which is approximately \(1 - 6.01 \times 10^{-3}\) when \(N = 2 \times 10^5\).

The following techniques can reduce the probability of failure.

1. Using two \(64\)-bit primes

In an implementation that assumes a one-to-one correspondence between prefix sums modulo \(P\) and positions, the bottleneck is that \(\sum_{i=1}^l 2^{A_i} \not\equiv \sum_{i=1}^r 2^{A_i} \bmod P\ (\star)\) must hold if \(l < r\), and the probability of failure is at most \(2 \times 1.67 \times 10^{-14} \cdot N(N+1)/2 \approx 6.68 \times 10^{-4}\).

Furthermore, if we randomly pick \(P\) until \((\star)\) is satisfied, the probability of failure is at most \((1.67 \times 10^{-14})^2 \times \frac{N(N+1)}{2}(\lfloor \log_2 N \rfloor + 1) \approx 1.00 \times 10^{-16}\).

2. Randomly picking a \(64\)-bit prime, solving the problem five times, and outputting the majority answer

The failure probability is at most approximately \(\binom{5}{3}(6.01 \times 10^{-3})^3 \approx 2.17 \times 10^{-6}\).

3. Using a \(128\)-bit prime

By a similar probability analysis, the failure probability can be bounded by approximately \(10^{-22}\).

Note that while the theoretical probability bound for using a single \(64\)-bit prime was \(6.01 \times 10^{-3}\), the actual probability is expected to be much lower. (Practical probability estimate: assuming each element of the prefix sums is random, the probability of outputting the correct answer with a single prime is approximately \(1 - \dfrac{N^2 \log_2 N}{P}\).)