Double Shuffle (Hard)

**This is the hard version of the problem. The only difference between this and the easy version is that here, $1 \leq Q \leq 2\cdot 10^5$. This problem is worth $50$ points.** You're given a permutation$^\dagger$ $P$ of the integers $1$ to $N$. There is beauty in order, so you'll only be satisfied if $P$ is sorted in ascending order, i.e. $P_i \lt P_{i+1}$ for each index $i$ from $1$ to $N-1$