1
class Solution {
2
 public:
3
  vector<int> tree;
4
  void build(vector<int> &nums) {
5
    int n = nums.size();
6
    for (int i = 0; i < nums.size(); i++) tree[i + n] = nums[i];
7
    for (int i = n - 1; i > 0; i--) tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
8
  }
9

10
  int query(int l, int r, int n) {
11
    l += n, r += n;
12
    int ans = INT_MAX;
13
    while (l < r) {
14
      if (l & 1) ans = min(ans, tree[l++]);
15
      if (r & 1) ans = min(ans, tree[--r]);
16
      l >>= 1;
17
      r >>= 1;
18
    }
19
    return ans;
20
  }
21

22
  int partitionDisjoint(vector<int> &nums) {
23
    int n = nums.size();
24
    int mx = -1;
25
    tree.resize(2 * n, INT_MAX);
26
    build(nums);
27
    for (int left = 0; left < n; left++) {
28
      mx = max(mx, nums[left]);
29
      if (query(left + 1, n, n) >= mx) return left + 1;
30
    }
31
    return n;
32
  }
33
};