P2839 [CTT] middle

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.

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 $Q$ lines in order, each giving the answer to a query.

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