题目描述

小红有一个长度为$n$的数组$a$，他想要使得数组$a$有序(单调不降），他必须选择一段区间$[l,r](1\le l,r\le n)$，将数组的这一段删除，其他的部分(如果存在的话)就按顺序拼在一起。 现在他想知道有多少种不同的选择区间的方案。

思路1：枚举+二分

考虑任选一个区间 $[l, r]$ 删除，剩余的左部分是 $[1,l-1]$ ，右部分是 $[r+1,n]$

需要保证 $a[1,l-1]$ 是单调递增，$a[r+1,n]$ 也是单调递增的，且满足 $a[l-1]\leq a[r+1]$

枚举区间 $[l,r]$ 的左端点 $left$，，来二分出区间的右端点 $right$，check 函数是 $a[left-1]\leq a[right+1]$

我们需要保证 $a[1]\leq a[2]\leq \cdots\leq a[left-1]$ ，所以枚举左端点 $left$ ，直到 $a[left]<a[left-1]$ 停止。