ABC 435

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    cout << N * (N + 1) / 2 << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;

    vll A(N);
    rep(i, N) cin >> A[i];

    fenwick_tree<ll> fw(N);
    rep(i, N) fw.add(i, A[i]);

    ll ans = 0;
    rep(i, N) rep2(j, i, N) {
        ll sum = fw.sum(i, j + 1);
        int div = 0;
        rep2(k, i, j + 1) {
            if (sum % A[k] == 0) div = 1;
        }
        if (!div) ans++;
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll A(N + 1);
    rep(i, N) cin >> A[i + 1];

    ll id = 2, nx = A[1] + 1;
    ll ans = 1;
    while (id <= N) {
        if (id < nx) {
            ans++;
        } else {
            break;
        }
        chmax(nx, id + A[id]);
        id++;
    }

    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;

    vvint graph(N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[v].push_back(u);
    }

    vint col(N);

    auto dfs = [&](auto dfs, int now) -> void {
        if (col[now]) return;
        col[now] = 1;

        for (int nx : graph[now]) {
            if (col[nx]) continue;
            dfs(dfs, nx);
        }
    };

    int Q;
    cin >> Q;
    rep(i, Q) {
        int t, v;
        cin >> t >> v;
        v--;
        if (t == 1) {
            dfs(dfs, v);
        } else {
            yesno(col[v]);
        }
    }
}

struct S {
    ll num_white;
};

S op(S a, S b) {
    return S{
        a.num_white + b.num_white,
    };
}

S e() {
    return S{0};
}

using F = ll;

S mapping(F f, S x) {
    if (f == 1) return S{0};  // 区間を黒く塗る
    return x;                 // 区間に対して何もしない. 何もしないときは id() の値が来る
}

F composition(F f, F g) {
    return f | g;
}

F id() {
    return 0;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, Q;
    cin >> N >> Q;

    vll L(Q), R(Q);
    rep(i, Q) {
        cin >> L[i] >> R[i];
        L[i]--;
    }

    vll pos = {0, N};
    for (auto x : L) pos.push_back(x);
    for (auto x : R) pos.push_back(x);
    sort(all(pos));
    pos.erase(unique(all(pos)), pos.end());

    int sz = (int)pos.size() - 1;
    vector<S> a(sz);
    rep(i, sz) {
        ll len = pos[i + 1] - pos[i];
        a[i] = S{len};
    }
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);

    rep(i, Q) {
        int l = lower_bound(all(pos), L[i]) - pos.begin();
        int r = lower_bound(all(pos), R[i]) - pos.begin();
        seg.apply(l, r, 1);
        S ret = seg.prod(0, sz);
        cout << ret.num_white << '\n';
    }
}