Min-Max Deque

**This is the hard version of the problem. Here, there are updates to the array, and the constraints on $Q$ are $1 \le Q \le 2 \cdot 10^5$.** Consider an array $A$ of length $N$. $N$ is odd. Alice and Bob will play the following game on it: - Let $B$ be an initially empty array. - Alice and Bob take turns playing, with Alice going first. - On the $i$-th turn, the current player will choose elem