[国家集训队]middle

题目背景

原《畅通工程》见1536

题目描述

一个长度为n的序列a,设其排过序之后为b,其中位数定义为b[n/2],其中a,b从0开始标号,除法取下整。 给你一个长度为n的序列s。 回答Q个这样的询问:s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中,最大的中位数。 其中a

输入输出格式

输入格式


第一行序列长度n。 接下来n行按顺序给出a中的数。 接下来一行Q。 然后Q行每行a,b,c,d,我们令上个询问的答案是x(如果这是第一个询问则x=0)。 令数组q={(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n}。 将q从小到大排序之后,令真正的要询问的a=q[0],b=q[1],c=q[2],d=q[3]。 输入保证满足条件。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

271451044
271451044
969056313

说明

0:n,Q<=100 1,...,5:n<=2000 0,...,19:n<=20000,Q<=25000