1520F2 · Guess the K-th Zero (Hard version)

Problem: This is an interactive problem.

This is a hard version of the problem. The difference from the easy version is that in the hard version $1 \le t \le \min(n, 10^4)$ and the total number of queries is limited to $6 \cdot 10^4$.

Polycarp is playing a computer game. In this game, an array consisting of zeros and ones is hidden. Polycarp wins if he guesses the position of the $k$-th zero from the left $t$ times.

Polycarp can make no more than $6 \cdot 10^4$ requests totally of the following type:

• ? $l$ $r$ — find out the sum of all elements in positions from $l$ to $r$ ($1 \le l \le r \le n$) inclusive.

To make the game more interesting, each guessed zero turns into one and the game continues on the changed array. More formally, if the position of the $k$-th zero was $x$, then after Polycarp guesses this position, the $x$-th element of the array will be replaced from $0$ to $1$.

Help Polycarp win the game.

Note: In the first test, the array $[1, 0, 1, 1, 0, 1]$ is hidden. After answering the query $k=2$, the array changed to $[1, 0, 1, 1, 1, 1]$.