不妨套用P9058的套路，记点对\((i,j),a_i\gea_j\)被支配当且仅当存在\(i<k<j\)，满足\(a_i\gea_k\gea_j\)，同样，猜测对于\(i\)，不被支配的点对\((k,i)\)只满足\(k<i\)最大且\(a_k>a_i\)。证明不妨使用反证法，记\(pre\)，满足\(pre<j<i\)且\(a_{pre},a_j>a_i\)，假设\((p

首先，如果你写过P9058的话，应该会想到支配点对这个trick,我们不妨将此题的套路搬到这套题上.定义点对\((i,j),a_i\lea_j\)，当\((i,j)\)被支配当且仅当存在\(i<k<j\)满足\(a_i\lea_k\lea_j\)。相应的，一个有效的点对\((i,j)\)，其中\(i\)满足\(i\)最大且\(a_i<a_j\)。