因为是排列，所以数对总数是调和级数的 \(O(n\log n)\)，可以暴力枚举。
容斥，区间左右端点均在 \([l,r]\) 中的数对数量等于左右端点均在 \([1,r]\) 中的数对数量减去左右端点均在 \([1,l-1]\) 中的数对数量，再减去左端点在 \([1,l-1]\) 中且右端点在 \([l,r]\) 中的数对数量。
发现前两个的形式是一样的，而且很好算，只要从小到大枚举右端点然后套路地用树状数组统计即可。
对于后面这部分，我们从小到大枚举它的分界点即 \(l\)，这样左端点就被限制好了，接着用树状数组统计合法的右端点数量即可。
时间复杂度 \(O(n\log^2 n)\)。因为都是从小到大枚举，所以把询问复制一份用两种方式排序后，用一个循环一个树状数组就可以统计，写起来会方便一点。