const int MAXN = 50000;
 
class SegmentTree {
public:
      int LSON[MAXN]; //LSON[i]為節(jié)點i的左兒子的序號
      int RSON[MAXN]; //RSON[i]為節(jié)點i的右兒子的序號
      int B[MAXN]; //B[i]為區(qū)間i左端點
      int E[MAXN]; //E[i]為區(qū)間i右端點
      int cnt[MAXN]; //cnt[i]為區(qū)間i的計數(shù)器
      int M[MAXN]; //M[i]為區(qū)間i的測度
      int lbd[MAXN]; //lbd[i]為區(qū)間i的左端點是否被覆蓋
      int rbd[MAXN]; //rbd[i]為區(qū)間i的右端點是否被覆蓋
      int lines[MAXN]; //lines[i]為區(qū)間i的連續(xù)線段數(shù)
      int root; //樹根 初始化時候設(shè)為1
      int n; //樹的節(jié)點數(shù)
      SegmentTree(int, int);
      void build(int, int);
      void insert(int, int, int);
      void del(int, int, int);
      void updateM(int); //更新測度
      void updateLines(int); //更新連續(xù)線段數(shù)
};
SegmentTree::SegmentTree(int a, int b) {
      root = 1;
      n = 0;
      memset(LSON, 0, sizeof(LSON));
      memset(RSON, 0, sizeof(RSON));
      memset(cnt, 0, sizeof(cnt));
      memset(M, 0, sizeof(M));
      memset(lines, 0, sizeof(lines));
      memset(lbd, 0, sizeof(lbd));
      memset(rbd, 0, sizeof(rbd));
      build(a, b);
}
void SegmentTree::build(int a, int b) {
      n += 1;
      int v = n;
      B[v] = a; E[v] = b; 
      if (b - a > 1) {
            LSON[v] = n + 1;
            build(a, (a+b)/2);
            RSON[v] = n + 1;
            build((a+b)/2, b);
      }
}
void SegmentTree::insert(int a, int b, int v) {
      if (!v) return ;
      if (a <= B[v] && E[v] <= b) {
            cnt[v]++;
            lbd[v] = rbd[v] = 1;
      } else if (E[v]-B[v] > 1) {
            if (a <(b[v]+e[v])/2) insert(a, b, LSON[v]);
            if (b > (B[v]+E[v])/2) insert(a, b, RSON[v]);
      }
      updateM(v);
      updateLines(v);
}
void SegmentTree::del(int a, int b, int v) {
      if (!v) return ;
      if (a <= B[v] && E[v] <= b) {
            cnt[v]--;
            if (a == B[v]) lbd[v] = 0;
            if (b == E[v]) rbd[v] = 0;
      } else if (E[v]-B[v] > 1) {
            if (a <(b[v]+e[v])/2) del(a, b, LSON[v]);
            if (b > (B[v]+E[v])/2) del(a, b, RSON[v]);
      }
      updateM(v);
      updateLines(v);
}
void SegmentTree::updateM(int v) {
      if (cnt[v] > 0) M[v] = E[v] - B[v];
      else {
            if (E[v]-B[v] == 1) M[v] = 0;
            else M[v] = M[LSON[v]] + M[RSON[v]];
      }
}
void SegmentTree::updateLines(int v) {
      if (cnt[v] > 0) lbd[v] = rbd[v] = lines[v] = 1;
      else {
            if (E[v]-B[v] == 1) lbd[v] = rbd[v] = lines[v] = 0;
            else {
                  lbd[v] = lbd[LSON[v]]; rbd[v] = rbd[RSON[v]];
                  lines[v] = lines[LSON[v]] + lines[RSON[v]] - rbd[LSON[v]] * lbd[RSON[v]];
            }
      }
}