#include <bits/stdc++.h>

using namespace std;

struct SegTree {
  struct Node {
    long long sum, minp;
    int freq;
  };
  vector<int> v;
  int n;
  vector<Node> T;

  SegTree(vector<int> v) : v(v), n(v.size()), T(4 * n) {
    init(1, 0, n - 1);
  }

  void pull(int node) {
    Node l = T[2 * node], r = T[2 * node + 1];
    T[node].sum = l.sum + r.sum;
    if (l.minp < l.sum + r.minp) {
      T[node].minp = l.minp;
      T[node].freq = l.freq;
    } else if (l.minp > l.sum + r.minp) {
      T[node].minp = r.minp + l.sum;
      T[node].freq = r.freq;
    } else {
      T[node].minp = l.minp;
      T[node].freq = l.freq + r.freq;
    }
  }

  void init(int node, int b, int e) {
    if (b == e) T[node] = Node{v[b] - b, v[b] - b, 1};
    else {
      int m = (b + e) / 2;
      init(node * 2, b, m);
      init(node * 2 + 1, m + 1, e);
      pull(node);
    }
  };

  void upd(int node, int b, int e, int l, int r) {
    if (e < l) return;
    if (b > r) return;
    if (b > l && e < r) return;
    if (b == e) {
      assert(b == l || b == r);
      T[node] = Node{v[b] - b, v[b] - b, 1};
      return;
    }
    int m = (b + e) / 2;
    upd(node * 2, b, m, l, r);
    upd(node * 2 + 1, m + 1, e, l, r);
    pull(node);
  }

  void Swap(int a, int b) {
    if (a > b) swap(a, b);
    swap(v[a], v[b]);
    upd(1, 0, n - 1, a, b);
  }

  int Get() {
    assert(T[1].minp == 0);
    return T[1].freq;
  }
};

struct Brut {
  vector<int> v;

  Brut(vector<int> v) : v(v) {}

  int Get() {
    int minn = v[0], maxx = v[0], ans = 0;
    for (int i = 0; i < (int)v.size(); ++i) {
      minn = min(minn, v[i]);
      maxx = max(maxx, v[i]);
      if (minn == 0 && maxx == i) {
        ans += 1;
      }
    }
    return ans;
  }

  void Swap(int a, int b) { swap(v[a], v[b]); }
};

int main() {
  int n = 20;
  vector<int> v(n);
  for (int i = 0; i < n; ++i)
    v[i] = i;
  SegTree st(v); Brut brut(v);
  for (int ops = 1;; ++ops) {
    int a = rand() % n, b = rand() % n;
    if (a == b) { --ops; continue; }
    st.Swap(a, b);
    brut.Swap(a, b);
    if (st.Get() != brut.Get()) {
      for (int i = 0; i < n; ++i)
        cerr << brut.v[i] << " "; cerr << endl;
      cerr << brut.Get() << " " << st.Get() << endl;
      return -1;
    }
    assert(st.Get() == brut.Get());
    if (ops % 1000 == 0) cerr << "OK " << ops << endl;
  }
}