#include #include #include const int N = 3e5 + 10; const int inf = 1e9 + 7; struct node_t { node_t *l, *r; int size, value, add; node_t() = default; node_t(int v): l(0), r(0), size(1), value(v), add(0) {} node_t* update() { size = 1; if (l) size += l->size; if (r) size += r->size; return this; } void mark(int v) { value += v; add += v; } void push() { if (add) { if (l) l->mark(add); if (r) r->mark(add); add = 0; } } } nodes[N]; node_t* build(node_t* l, node_t *r) { node_t* m = l + (r - l) / 2; if (l < m) m->l = build(l, m - 1); if (m < r) m->r = build(m + 1, r); m->update(); return m; } int get_size(node_t *o) { return o ? o->size : 0; } bool random(int a, int b) { return rand() % (a + b) < a; } std::pair split_by_value(node_t *o, int v) {//[-inf, v), [v, +inf) node_t *l = 0, *r = 0; if (!o) return {l, r}; o->push(); if (o->value < v) { std::tie(o->r, r) = split_by_value(o->r, v); l = o; } else { std::tie(l, o->l) = split_by_value(o->l, v); r = o; } o->update(); return {l, r}; } std::pair split_by_size(node_t *o, int size) {//[0, size), [size, +inf) node_t *l = 0, *r = 0; if (!o) return {l, r}; o->push(); int ls = get_size(o->l); if (ls < size) { std::tie(o->r, r) = split_by_size(o->r, size - ls - 1); l = o; } else { std::tie(l, o->l) = split_by_size(o->l, size); r = o; } o->update(); return {l, r}; } node_t* merge(node_t *l, node_t *r) { if (!l || !r) return l ? l : r; l->push(); r->push(); if (random(l->size, r->size)) { l->r = merge(l->r, r); return l->update(); } else { r->l = merge(l, r->l); return r->update(); } } void print(node_t *o) { if (!o) return; o->push(); print(o->l); printf("%d ", o->value); print(o->r); } int main() { int T; T = 1; for (int cas = 1; cas <= T; ++cas) { int n; scanf("%d", &n); for (int i = 0; i <= n; ++i) nodes[i] = node_t(inf); node_t* root = build(nodes, nodes + n + 1); for (int i = 0; i < n; ++i) { int l, r; scanf("%d%d", &l, &r); node_t *a, *b, *c, *d; std::tie(b, d) = split_by_value(root, r); std::tie(a, b) = split_by_value(b, l); std::tie(c, d) = split_by_size(d, 1); c->value = l; if (b) b->mark(1); root = merge(merge(a, c), merge(b, d)); } node_t *x, *y; std::tie(x, y) = split_by_value(root, inf); printf("%d\n", x->size); } return 0; }