小明这些天一直在思考这样一个奇怪而有趣的问题： 在 1∼N 的某个排列中有多少个连号区间呢？ 这里所说的连号区间的定义是： 如果区间 LR 里的所有元素即此排列的第 L 个到第 R 个元素递增排序后能得到一个长度为 R−L+1 的连续数列则称这个区间连号区间。 当 N 很小的时候小明可以很快地算出答案但是当 N 变大的时候问题就不是那么简单了现在小明需要你的帮助。 输入格式

算法

(归并排序)

这是一道比较经典的区间统计问题，暴力做法是枚举所有区间，然后判断是否是连号区间，时间复杂度 $O(n^3)$ 显然会超时。

我们可以考虑用分治的思想来优化这个时间复杂度，具体来说，可以使用归并排序，记录每个区间内的连号区间数量，然后在归并的时候计算跨越左右两个区间的连号区间数量。

时间复杂度

归并排序的时间复杂度是 $O(n \log n)$，每个区间内的连号区间数量可以在 $O(n)$ 时间内计算，因此总时间复杂度是 $O(n \log n)$。

C++ 代码

时间复杂度 $O(n \log n)$