Description

Given a sequence $a$ of length $n$, let $b$ be the sorted version of $a$. The median is defined as $b_{n/2}$, where $a$ and $b$ are 0-indexed and the division takes the floor.

You are given a sequence $s$ of length $n$.

Answer $Q$ queries of the following type: among all subarrays of $s$ whose left endpoint is in $[a, b]$ and right endpoint is in $[c, d]$, find the maximum possible median.

Here $a < b < c < d$.

Positions are also 0-indexed.

I will use some method to force you to process the queries online.

Input Format

The first line contains the sequence length $n$.

The next $n$ lines give the numbers of $s$ in order.

The next line contains $Q$.

Then $Q$ lines follow, each containing $a, b, c, d$. Let the answer to the previous query be $x$ (if this is the first query, then $x=0$).

Let the array $q=\{(a+x)\bmod n,(b+x)\bmod n,(c+x)\bmod n,(d+x)\bmod n\}$.

After sorting $q$ in ascending order, let the actual query be $a=q_0$, $b=q_1$, $c=q_2$, $d=q_3$.

The input is guaranteed to satisfy the conditions.

Output Format

Output $Q$ lines in order, each giving the answer to a query.

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

271451044
271451044
969056313

Hint

For $5\%$ of the testdata, $n, Q \leq 100$.

For an additional $25\%$ of the testdata, $n \leq 2000$.

For $100\%$ of the testdata, $1 \leq n \leq 20000$, $1 \leq Q \leq 25000$, $1 \leq s_i \leq 10^9$.

Translated by ChatGPT 5