203017 - 稳定子数组

给你一个长度为n的正整数数组a，如果a的一个连续子数组中没有逆序对，即不存在满足i<j且a[i]>a[j]的下标对，则该子数组被称为稳定子数组。 现在有q个询问，每个询问需要统计完全包含在a[li,⋯ri]内的稳定子数组的数量。

第一行包含2个正整数n,q(1≤n,q≤10^5)，表示数组a的长度和询问个数。 第二行包含n个正整数，表示数组a。 接下来q行，每行包含2个数li，ri(0≤li,ri≤n−1)。

输出1行包含q个数，表示每个询问的答案。

样例1中，对于询问[li,ri]=[0,1]，子数组为[3,1]，稳定子数组包括[3]和[1]，稳定子数组的总数为2。子数组[3,1]包含逆序对。 对于询问[li,ri]=[1,2]，子数组为[1,2]，稳定子数组包括[1]，[2]，[1,2]，稳定子数组的总数为3。 对于询问[li,ri]=[0,2]，子数组为[3,1,2]，稳定子数组包括[3]，[1]，[2]，[1,2]，稳定子数组的总数为4。