Breaking Down News

It is preferrable to read the pdf statment.

Cuber QQ, who is the producer of Breaking News, is tired of all the pressures from producing high-quality content and making sponsors happy. The most painful part of this job is, actually, to put all the news clips into units, between which advertisements are broadcast. Recently, after acquiring some knowledge from technology department, he found that he can actually leverage some help from algorithms.

Formally, the sequence of news clips to be broadcast tonight is a sequence $a$ consisting of $n$ integers, where $a=a_1,a_2,\ldots,a_n$ ($a_i\in \{-1,0,1\}$), which are the expected quality of those news clips. Being of negative quality does not mean that the clip will not be broadcast. Actually all the contents have already been carefully selected to fit the length of the TV show. Also, the clips should follow the order, which is already carefully arranged.

To insert ads between clips, Cuber QQ asks you to split the sequence into $m$ ($m \ge 1$) non-empty units, i.e., consecutive subsequences, so that every clip belongs to exactly one unit. Formally, if the $k$-th unit is $a_{l_k},a_{l_k+1},\cdots ,a_{r_k}$, then $r_k+1=l_{k+1}$ for all $1\le k < m$.

Furthermore, each unit should be of moderate length, neither too long nor too short. Formally, $L \le r_i-l_i+1\le R$ should hold for all $1\le k \le m$.

The quality of a unit, is defined to be 1 if quality sum of its corresponding clips is greater than 0, -1 if the sum is lower than 0, and 0 otherwise. This can be formulated with $v_k= [(\sum_{i=l_k}^{r_k} a_i ) > 0]-[(\sum_{i=l_k}^{r_k} a_i ) < 0]$.

The problem is to determine the optimal $m$ and the split plan, to maximize the sum of values of all units, i.e., to maximize $\sum_{k=1}^m v_k$.

The first line of the input contains a single integer $T$ ($1\le T\le 1~000$), denoting the number of test cases.

For each of the next $T$ cases:

• The first line contains three space-separated integers $n$, $L$, $R$ ($1\le L\le R \le n\le 10^6$).


• The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($a_i\in \{-1,0,1\}$).

It is guaranteed that at least one valid split exists.

The sum of $n$ in all test cases doesn't exceed $9\cdot 10^6$.

For every test case, output one line containing an integer, denoting the maximum value.

3
5 1 5
1 -1 0 -1 1
5 5 5
-1 1 -1 1 -1
5 1 1
1 -1 0 -1 1

1
-1
0

2020 Multi-University Training Contest 8