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?

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.

Consider an easier problem:for a fixed score $$$x_1*x_2*...*x_k$$$($$$x_i$$$ is one of the prefix minimum value),how to calculate the number of schemes?

Consider such a sequence construction process: put all $$$0$$$'s, all $$$1$$$'s, and all $$$2$$$'s,...

If you want the prefix minimum value of $$$i$$$ to appear in $$$a$$$, what should you do?We can get:at least one $$$i$$$ must be placed at the head of the current sequence.

This is actually equivalent to the classical problem: $$$m_i$$$ balls are put into $$$(m_1+...+m_{i-1}+1)$$$ boxes, the first box must have at least one ball,count the number of schemes.

The answer is:

$$$U_i=C(m_i-1+(m_1+...+m_{i-1}),(m_1+...+m_{i-1}))$$$.

If you want the prefix minimum value of i not to appear in $$$a$$$, what should you do?We can get:no $$$i$$$ must be placed at the head of the sequence.Solve it in a similar way as above.

The answer is:

$$$V_i=C(m_i+(m_1+...+m_{i-1})-1,(m_1+...+m_{i-1})-1)$$$.

Let's go back to the easier problem.The number of schemes is $$$\Phi_{i∈X}U_i * \Phi_{i∉X}V_i$$$.

If you know the pre-min set S of A, how to find the number of schemes?For example,N=5,S={1,3,5},the number is:U[1]*V[2]*U[3]*V[4]*U[5].

Finally, how to calculate the total score?With some tricks, we can convert the formula into:(1*U[1]+V[1])(2*U[2]+V[2])...(N*U[N]+V[N]).

1