A Simple Problem

Pair View

The title is trolling you a bit. The clean way is to count inversions by looking at the right endpoint of each pair.

For a fixed subarray $b$, write

$$M_i=\max_{1\le j\le i} b_j,\qquad m_i=\min_{1\le j\le i} b_j.$$

For a pair $i<j$:

• If $c_j=M_j$, then $c_i\le M_j$, so this pair is never an inversion.
• If $c_j=m_j$, then every earlier position whose prefix minimum is larger than $m_j$ is automatically an inversion. Inside the same prefix-minimum block, exactly the earlier positions chosen as prefix maximum are inversions.

So choices only interact inside blocks with equal prefix minimum. Blocks with different prefix minimum talk to each other in the dumbest possible way: a later minimum loses to every earlier element.

One Block

Split the query into consecutive blocks where $m_i$ is constant. Suppose a non-first block has length $T$, and $S$ positions are before it. If $X$ positions in this block are chosen as prefix maximum, putting those $X$ choices first is optimal, because only max-before-min pairs inside the block matter.

The contribution is

$$g(S,T,X)=S(T-X)+X(T-X)=(S+X)(T-X).$$

This is a concave quadratic, so

$$X=\operatorname{clamp}\left(\left\lfloor\frac{T-S}{2}\right\rfloor,0,T\right)$$

is optimal. When $T\le S$, this gives $X=0$, i.e. choose all prefix minima and gain $ST$ inversions.

The first block has one special nuisance: at the first position, prefix minimum and maximum are equal. It contributes nothing inside that block, so for first-block length $T$ the answer is

$$\max_X X(T-1-X)=\left\lfloor\frac{(T-1)^2}{4}\right\rfloor.$$

Where The Blocks Come From

For the whole permutation, define $nxt[i]$ as the first index $j>i$ with $p_j<p_i$, or the sentinel $n$ if it does not exist. This is found by a monotonic stack.

For a query $[l,r)$, the prefix-minimum block starts are

$$l,\ nxt[l],\ nxt[nxt[l]],\ldots$$

until we leave the query. The block starting at $u$ has full length $d_u=nxt[u]-u$, except the last one may be cut by $r$.

Jumping The Boring Blocks

If a block has $T>S$, then after processing it the processed length becomes $S+T>2S$. So this scary case happens only $O(\log n)$ times. Nice. The rest are blocks with $T\le S$, where the contribution is just $S\cdot T$.

For several consecutive full boring blocks with lengths $d_1,d_2,\ldots,d_k$ and initial processed length $S$, their total contribution is

$$S d_1+(S+d_1)d_2+\cdots+(S+d_1+\cdots+d_{k-1})d_k =SD+\frac{D^2-\sum d_i^2}{2},$$

where $D=\sum d_i$. So we only need $D$ and $\sum d_i^2$ for a chain segment.

Precompute binary lifting on the $nxt$ chain:

• $pa[u][k]$ is the $2^k$-th jump by $nxt$.
• $sum1[u]$ and $sum2[u]$ are suffix sums of $d$ and $d^2$ along the chain.
• $up[u][k]$ is the first node on the chain from $u$ whose full block length is at least $2^k$.

Since $nxt[u]>u$, all of this can be filled from right to left.

During a query, let $S$ be the processed length and $u$ the current block start. Put $K=2^{\lfloor\log_2 S\rfloor}$. Every block before $up[u][\log_2 K]$ has length $<K\le S$, hence it is boring and can be aggregated with the formula above. Then process the stopping block directly using the quadratic. If the jump goes past $r$, use $pa$ to stop at the last block start inside the query.

Each direct block processing either ends the query, handles a $T>S$ block, or handles a block with $T\ge S/2$; in all cases there are only $O(\log n)$ such steps. The extra border search costs another $O(\log n)$.

Complexity

The preprocessing is $O(n\log n)$ per test case. Each query is $O(\log^2 n)$ with this straightforward lifting implementation, and the memory usage is $O(n\log n)$. With $\sum n,\sum q\le 10^6$, this is comfortably fine.

Reference checked while verifying the optimization: official Codeforces Round 1089 editorial.