1
// itne me hi thakk gaye?
2
class Solution {
3
 public:
4
  bool ok(int &size, vector<int> &pref, vector<int> &suff, vector<int> &arr, int &n) {
5
    for (int start = 0; start <= n - size; start++) {
6
      int end = start + size - 1;
7
      int left = (start <= 0) ? 0 : pref[start - 1];
8
      int right = (end >= n - 1) ? 0 : suff[end + 1];
9
      int le = (start <= 0) ? -1e9 + 2 : arr[start - 1];
10
      int re = (end >= n - 1) ? 1e9 + 2 : arr[end + 1];
11
      if (left + right == n - size && le <= re) {
12
        return true;
13
      }
14
    }
15
    return false;
16
  }
17
  int findLengthOfShortestSubarray(vector<int> &arr) {
18
    int n = arr.size();
19
    if (!n || n == 1) return 0;
20
    vector<int> pref(n, 1);
21
    vector<int> suff(n, 1);
22
    for (int i = 1; i < n; i++) {
23
      if (arr[i] >= arr[i - 1]) pref[i] = pref[i - 1] + 1;
24
    }
25
    for (int i = n - 2; i >= 0; i--) {
26
      if (arr[i] <= arr[i + 1]) suff[i] = suff[i + 1] + 1;
27
    }
28
    int low = 0;
29
    int high = n - 1;
30
    while (low < high) {
31
      int mid = (low + high) / 2;
32
      if (ok(mid, pref, suff, arr, n))
33
        high = mid;
34
      else
35
        low = mid + 1;
36
      if (high - low == 1) break;
37
    }
38
    if (ok(low, pref, suff, arr, n)) return low;
39
    return high;
40
  }
41
};