Readme

2972.Count-the-Number-of-Incremovable-Subarrays-II

本题最直观的考虑，就是将数组分成三段（考虑1-index）：前段[1:i]，中段[i+1:j-1]，以及后段[j:n]。其中要移走中段，而前段和后段必须各自都是严格递增的。于是我们可以找到i的最大位置记做L，以及j的最小位置记做R。

  int l = 1;
  while (l<=n)
  {
      if (nums[l]<nums[l+1]) l++;
      else break;
  }
  int r = n;
  while (r>0)
  {
      if (nums[r]>nums[r-1]) r--;
      else break;
  }

对于[1:L]里的每一个位置i，我们可以在[R,n]用二分找到恰好大于nums[i]的位置j。那么符合条件的后段的左边界可以是j,j+1,...,n，总共有n+1-j个。

但是以上的思考意识强制要求前段、中段、后段都不能为空，而忽略了对应的三种情况：前段为空，中段为空、或者后段为空。需要额外考虑。

1. 如果中段为空，那么说明nums整体都是递增的，直接返回nums里的子区间的数目：n(n-1)/2+n.
2. 如果前端为空，或者后端为空，我们可以有一个巧妙的处理，使得之前的逻辑依然适用。在nums前添加一个无穷小（index是0），后面添加一个无穷大（index是n+1）。这样，i的遍历可以从0开始（意味着其实左段为空）；而在[R:n+1]区间里进行二分的过程中可能会找到n+1这个位置（即认为后段的左边界是n+1），这其实就意味着允许了后段为空。