bzoj#P2653. middle

middle

题目描述

一个长度为 nn 的序列 aa,设其排过序之后为 bb,其中位数定义为 bn2b_{\lfloor\frac{n}{2}\rfloor},其中 a,ba,b00 开始标号,除法取下整。

给你一个长度为 nn 的序列 ss

回答 QQ 个这样的询问:ss 的左端点在 [a,b][a,b] 之间,右端点在 [c,d][c,d] 之间的子区间中,最大的中位数。

其中 a<b<c<da<b<c<d。位置也从 00 开始标号。

我会使用一些方式强制你在线。

输入格式

第一行序列长度 nn

接下来 nn 行按顺序给出 aa 中的数。

接下来一行 QQ

然后 QQ 行每行 a,b,c,da,b,c,d,我们令上个询问的答案是 xx(如果这是第一个询问则 x=0x=0)。

令数组 $q=\{(a+x)\bmod n,(b+x)\bmod n,(c+x)\bmod n,(d+x)\bmod n\}$。

qq 从小到大排序之后,令真正的要询问的 a=q0,b=q1,c=q2,d=q3a=q_0,b=q_1,c=q_2,d=q_3

输入保证满足条件。

输出格式

QQ 行依次给出询问的答案。

样例

5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
271451044
271451044
969056313

数据范围与约定

对于 5%5\% 的数据, n,Q102n,Q \leq 10^2

对于另 25%25\% 的数据, n2×103n \leq 2\times 10^3

对于 100%100\% 的数据, n2×104n \leq 2\times 10^4Q2.5×104Q \leq 2.5\times 10^4