Summit (Hard)

**This is the hard version of the problem. The only difference between this and the easy version is the constraint on $N$: here, $N$ and the sum of $N$ are both $\leq 2\cdot 10^5$.** You are given a permutation$^\dagger$ $P$ of the integers $1$ to $N$. **At most once**, you can do the following operation: - Choose two indices $i$ and $j$ ($1 \leq i \lt j \leq N$) and swap $P_i$ and $P_j$. Fi