P15458 [MX-X25-T2] "FeOI-5" Powers of 2

You are given a non-negative integer sequence $a$ of length $n$. You may perform the following operation any number of times: 1. Choose an interval $[l,r]$ (where $l$ and $r$ may be equal). 2. Let $s=\sum \limits_{i\in [l,r]} a_i$, and let $k$ be the largest non-negative integer such that $2^k\le s$ (if $s=0$ then $k=0$). 3. You gain $k$ coins, and delete $a_{[l,r]}$. After that, $a_{[1,l-1]}$ and $a_{[r+1,n]}$ are concatenated, i.e., the new length of $a$ becomes $n-r+l-1$. Find the maximum number of coins you can obtain.

The first line contains two integers $c,T$, representing the subtask ID of the test point (the samples guarantee $c=0$) and the number of test cases. For each test case, the input contains two lines: - The first line contains an integer $n$. - The second line contains $n$ integers representing the sequence $a$.

For each test case, output one line with one integer representing the answer.

**Sample 1 Explanation** First operation: choose interval $[2,2]$. Then $s=2,k=1$, you gain $1$ coin, and the sequence becomes `3 1 1 4` after the operation. Second operation: choose interval $[1,3]$. Then $s=5,k=2$, you gain $2$ coins, and the sequence becomes `4` after the operation. Third operation: choose interval $[1,1]$. Then $s=4,k=2$, you gain $2$ coins, and the sequence becomes an empty sequence after the operation. In total you gain $5$ coins. It can be proven that this is the maximum number of coins that can be obtained. **Constraints** For all testdata, $1\le n,\sum n\le 10^6$, $0\le a_i\le 10^{18}$, $1\le T\le 100$. | Subtask ID | $\sum n$ | Special Property | Score | | :--------: | :------: | :--------------: | :---: | | $1$ | $\le 5$ | None | $5$ | | $2$ | $\le 100$ | None | $10$ | | $3$ | $\le 10^6$ | $0\le a_i\le 3$ | $10$ | | $4$ | $\le 10^6$ | $\forall i$，there does not exist $k$ such that $a_i=2^k-1$ | $20$ | | $5$ | $\le 5000$ | None | $20$ | | $6$ | $\le 10^6$ | None | $35$ | Translated by ChatGPT 5