{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\u003cb\u003eIt is preferrable to read the pdf statment.\u003c/b\u003e\u003cbr\u003e\u003cbr\u003eCuber 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.\u003cbr\u003e\u003cbr\u003eFormally, the sequence of news clips to be broadcast tonight is a sequence $a$ consisting of $n$ integers, where $a\u003da_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.\u003cbr\u003e\u003cbr\u003eTo 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\u003dl_{k+1}$ for all $1\\le k \u0026lt; m$.\u003cbr\u003e\u003cbr\u003eFurthermore, 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$.\u003cbr\u003e\u003cbr\u003eThe 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\u003d [(\\sum_{i\u003dl_k}^{r_k} a_i ) \u0026gt; 0]-[(\\sum_{i\u003dl_k}^{r_k} a_i ) \u0026lt; 0]$.\u003cbr\u003e\u003cbr\u003eThe 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\u003d1}^m v_k$.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains a single integer $T$ ($1\\le T\\le 1~000$), denoting the number of test cases.\u003cbr\u003e\u003cbr\u003eFor each of the next $T$ cases:\u003cbr\u003e\u003cbr\u003e\u003cul\u003e\u003cbr\u003e \u003cli\u003e The first line contains three space-separated integers $n$, $L$, $R$ ($1\\le L\\le R \\le n\\le 10^6$).\u003c/li\u003e\u003cbr\u003e \u003cli\u003e The second line contains $n$ integers $a_1,a_2,\\ldots,a_n$ ($a_i\\in \\{-1,0,1\\}$).\u003c/li\u003e\u003cbr\u003e\u003c/ul\u003e\u003cbr\u003e\u003cbr\u003eIt is guaranteed that at least one valid split exists.\u003cbr\u003e\u003cbr\u003eThe sum of $n$ in all test cases doesn\u0027t exceed $9\\cdot 10^6$."}},{"title":"Output","value":{"format":"HTML","content":"For every test case, output one line containing an integer, denoting the maximum value."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n5 1 5\r\n1 -1 0 -1 1\r\n5 5 5\r\n-1 1 -1 1 -1\r\n5 1 1\r\n1 -1 0 -1 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n-1\r\n0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}