时间限制：1秒　　内存限制：256M

---

【题目描述】

　　一个长度为 \(n\) 的序列 \(a\)，设其排过序之后为 \(b\)，其中位数定义为 \(b[n/2]\)，其中 \(a,b\) 从 0 开始标号，除法取下整。
　　给你一个长度为 \(n\) 的序列 \(s\)。回答 \(Q\) 个这样的询问：\(s\) 的左端点在 \([a,b]\) 之间，右端点在 \([c,d]\) 之间的子序列中，最大的中位数。其中：\(a < b < c < d\)。位置也从 0 开始标号。我会使用一些方式强制你在线。

【输入格式】

　　第一行序列长度 \(n\)。接下来的 \(n\) 行按顺序给出 \(a\) 中的数（序列中元素绝对值不超过 \(10^9\) ）。
　　再接下来一行 \(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\) 行依次给出询问的答案。

【输入输出样例】

　Input

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

　Output

271451044
271451044
969056313

【数据限制】

　　对于 \(20\%\) 的数据，\(n,q≤100\)
　　对于 \(50\%\) 的数据，\(n,q≤2000\)
　　对于 \(100\%\) 的数据，\[n≤20000\]，\(q≤2500\)

【来源】

　　Mr.he**