I enjoyed the problem, indeed.

Key observation

First,the $$$(i,j)$$$ must satisfy $$$a_i$$$ is the prefix minimum and the $$$a_j$$$ is the suffix maximum.Otherwise,the modification has no use or the $$$j$$$ can be adjusted to the next suffix maximum to its right.

Second,if the $$$x$$$ which the $$$a_i$$$ is changed to is bigger than the previous prefix minimum,it's all the same no matter the $$$x$$$ ranges.It's because the minimum has been taken by the last one.

$$$a_i\in [0,n]$$$,so the first property is the number of key pairs $$$(i,j)$$$ is $$$O(n)$$$.

So get the $$$O(n^2)$$$ brute force solution: https://mirror.codeforces.com/contest/2124/submission/327896282.

Solution

All we need to do is to solve a pair $$$(i,j)$$$ fast enough.

Denote $$$a_i:=x$$$,and divide the array into some parts.

$$$[1,i-1]$$$: precalculated.

Oh,the prefix minimum need another case work.

Find the minimum $$$k$$$,s.t. $$$i \lt k \lt j,x\leq a_k$$$.

$$$[i,k)$$$: prefix minimum are all x

But we need to handle whether $$$k \gt j$$$ or $$$j\leq k$$$,that's another case work.

to calculate $$$[k,j)$$$ that's not easy.So change the angle.

1.$$$[k,n]$$$: from a $$$a_k$$$ to get minimums, calculated in some way

2.$$$[j,n]$$$: from a value to get minimums,calculated in some other way.

3.combine them: subtract $$$[j,n]$$$ from $$$[k,n]$$$.

The techique details are in the code.(https://mirror.codeforces.com/contest/2124/submission/327901887)