Note $$$maxp$$$ as the maximum index of the maximum value in $$$a$$$.
For $$$1 \leq k \leq maxp-1$$$,they do not meet the condition.
For $$$maxp+1 \leq k \leq n$$$,they all meet the condition.
You need to be careful of $$$k==maxp$$$,it meet the condition if and only if there is only one maximum value in $$$a$$$.
Note $$$a_1$$$ as the first $$$\lceil{n/2}\rceil$$$ numbers of $$$a$$$,and $$$a_2$$$ as the last $$$n-\lceil{n/2}\rceil$$$ numbers of $$$a$$$.
Through observation,we found that the following processes will be repeated cyclically:
erase the leftmost number of $$$a_1$$$
erase the leftmost number of $$$a_2$$$
erase the rightmost number of $$$a_1$$$
erase the rightmost number of $$$a_2$$$
In conclusion:
If $$$|a_1|>|a_2|$$$(i.e. $$$n$$$ is odd),the answer is the number in the middle of $$$a_1$$$
If $$$|a_1|=|a_2|$$$(i.e. $$$n$$$ is even),the answer is the number in the middle of $$$a_2$$$
We notice we can convert condition $$$3$$$ to $$$c0(a,l_1,r_1)-c1(a,l_1,r_1)=c1(b,l_2,r_2)-c0(b,l_2,r_2)$$$.
This provides us with convenience: we can independently calculate the left and right value ranges.
If two ranges intersect, the answer is $$$YES$$$,otherwise the answer is $$$NO$$$.
Let's calculate the left value ranges.Make all $$$a_i=0$$$ to $$$1$$$ and $$$a_i=1$$$ to $$$-1$$$,it is the value range of all subarrays of appropriate length.
In fact,we only need to find max subsegment sum and min subsegment sum.It's a classic problem.
You may have already guessed:if $$$x_1<y_1$$$,and you get $$$minsum,maxsum$$$,the range of values is continuous — $$$[minsum,maxsum]$$$.Why?
Consider we have get $$$[L_1,R_1]$$$ which make $$$minsum$$$ and $$$[L_2,R_2]$$$ which make $$$maxsum$$$.
We use continuous transformation to make:$$$[L_1,R_1]->[L_2,R_2]$$$.
Step1:Length Adjustment
For convenience we assume $$$R_1-L_1+1>R_2-L_2+1$$$.
Transform:$$$[L_1,R_1]->[L_1+1,R_1]->[L_1+2,R_1]->...->[L_1',R_1]$$$ $$$(R_1-L_1'+1=R_2-L_2+1)$$$
Step2:"Creeping"
For convenience we assume $$$R_1<R_2$$$.
Transform:$$$[L_1',R_1]->[L_1'+1,R_1]->[L_1'+1,R_1+1]->...->[L_2,R_2]$$$
After once length adjustment and several times creeping,we have transformed $$$[L_1,R_1]$$$ to $$$[L_2,R_2]$$$ continuously and proved the value range is continuous.
You also need to be careful of the edge cases that $$$x_i=y_i(1 \leq i \leq 2)$$$.
We notice we can calculate each bit independently.
In other words,note $$$f(a_i,j)$$$ as the $$$j^{th}$$$ bit under the binary representation of $$$a_i$$$,the answer is $$$\Sigma_{i=0}^{i=30} 2^{i}*(\Sigma f(a_l,i)⊕...⊕f(a_r,i))$$$.
Let's calculate the sum of the $$$0^{th}$$$ bit.
$$$a_{i,0}=0,1,0,1,...$$$
Note $$$pre_{i,0}=a_{1,0}⊕...⊕a_{i,0}$$$,then
$$$pre_{i,0}=0,1,1,0,0,1,1,0,...$$$
We noticed that the loop section of this sequence is $$$4$$$ and can calculate the total number of '1'(note it as c_1).The total number of subarrays with xor-value $$$1$$$ is $$$c_1*(n+1-c_1)$$$.
For the $$$1,2,...30^{th}$$$ bit,use the similar method to calculate it.
1
1