有 \(n\) 个人，把他们划分成尽可能多的区间，其中第 \(i\) 个人要求它所在的区间长度大于等于 \(c_i\)，小于等于 \(d_i\)，求最多的区间数量以及如此划分的方案数。

数据范围：\(1\le n \le 10^6, 1\le c_i, d_i\le n\)。时间限制7s（优秀解500-700ms，我的垃圾大常数实现2s，我都觉得写假了）。

方案数是 trivial 的，实现一个 Data 类，合并信息的时候同时维护最大值和方案数即可。注意信息失去了幂等性。

首先考虑朴素 DP，设 \(f_i\) 表示前 \(i\) 个数可以划分成的最大区间数。转移枚举上一段的端点即可。时间复杂度 \(\Theta(n^2)\)。

下面考虑优化。注意到线性结构，转移彼此独立，考虑分治优化。题解区许多解法似乎是标准 CDQ 分治做法，然而时间复杂度是双 \(\log\) 的同时实现也较为复杂。我没有研究。

这题处理的难点在于我要同时维护 \(c\) 和 \(d\) 两个方向的限制，能转移到 \(i\) 的所有 \(j\) 分布很诡异，而 CDQ 分治并不能帮助改善这一点。而我们对于 \(c, d\) 关注的只有最值。这启示我们使用最值分治的做法，将其中一个的最值对应点放到分治中心，这样所有左区间到右区间的转移都会跨越这个点，它又是最值，相当于这一维限制被固定了。观察题目可以发现，\(d\) 作为上界限制，只考虑它限制下能对 \(i\) 进行转移的 \(j\) 一定是 \([0, i - 1]\) 的一段后缀，设为 \([pre_i, i - 1]\)，这个东西很好预处理，并且很优美（注意到 \(pre_i\) 不降），所以我们考虑固定 \(c\)，当前分治区间设为 \([l, r]\)，中点设为 \(mid\)（注意左区间是 \([l, mid)\)），那么能转移到右区间 \(i\) 的 \(j\) 所属区间是 \([l, mid)\cap [pre_i, i - c_{mid}]\)。

然而最值分治失去了分治层数 \(\log\) 的特性，一般地需要在合并时精细实现来避免退化成平方（我就退化过）。当然，分治区间总个数仍然保证是 \(\Theta(n)\) 的。接下来考虑分类转移：

1. \(i < l + c_mid\) 或者 \(pre_i \ge mid\)：很容易排除掉。

2. \(pre_i < l, i - c_{mid} < mid\)：区间是 \([l, mid)\) 的前缀，随着 \(i\) 不断增加，右端点只会每次移动 1，那么第一次在线段树上查一下，后面就直接用 \(f_j\) 来 \(\Theta(1)\) 更新即可。这一部分的时间复杂度：第一次查线段树 \(\Theta(n\log n)\)，后面的更新次数只会是左右区间长度的 \(\min\)，类比启发式合并可以得到时间复杂度是 \(\mathrm O(n\log n)\)。

3. \(pre_i < l, i - c_{mid} \ge mid\)：区间是 \([l, mid)\)，二分一下右边能被这样更新的 \(i\)，一定也是个区间，线段树上区间查一下，区间取 \(max\) 一下，\(\Theta(n\log n)\)。

4. \(pre_i \in [l, mid), i - c_{mid} \ge mid\)：全部暴力 \(\Theta(\log n)\)，这是因为对于一个 \(i\)，它所属的所有分治右区间，所对应的分治左区间两两不交（可以画出分治树看一下），所以 \(pre_i\) 只属于其中某一个，于是每个 \(i\) 只会这样暴力转移一次。

于是这样做完了，总复杂度 \(\Theta(n\log n)\)。

// Author: kyEEcccccc

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using ULL = unsigned long long;

#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)

const int N = 1000005, MOD = 1000000007;

int n, c[N], d[N];

struct Data { int mx; LL s; };

Data mer(Data x, Data y)
{
    Data r = {max(x.mx, y.mx), 0};
    if (x.mx == r.mx) r.s += x.s;
    if (y.mx == r.mx) (r.s += y.s) %= MOD;
    return r;
}

struct SegTree
{
    Data x[N << 2], tg[N << 2];

    void init(int p, int cl, int cr)
    {
        x[p] = tg[p] = {-n, 0};
        if (cl == cr) return;
        int cm = cl + cr >> 1;
        init(p << 1, cl, cm);
        init(p << 1 | 1, cm + 1, cr);
    }

    void pushdown(int p)
    {
        Data d = tg[p]; tg[p] = {-n, 0};
        x[p << 1] = mer(x[p << 1], d);
        x[p << 1 | 1] = mer(x[p << 1 | 1], d);
        tg[p << 1] = mer(tg[p << 1], d);
        tg[p << 1 | 1] = mer(tg[p << 1 | 1], d);
    }

    Data get_max(int p, int cl, int cr, int l, int r)
    {
        if (l > r) return {-n, 0};
        if (cl >= l && cr <= r) return x[p];
        pushdown(p);
        int cm = cl + cr >> 1;
        if (l <= cm && r > cm)
        {
            return mer(get_max(p << 1, cl, cm, l, r),
                get_max(p << 1 | 1, cm + 1, cr, l, r));
        }
        else if (l <= cm) return get_max(p << 1, cl, cm, l, r);
        else return get_max(p << 1 | 1, cm + 1, cr, l, r);
    }

    void assign_max(int p, int cl, int cr, int l, int r, Data d)
    {
        if (l > r) return;
        if (cl >= l && cr <= r)
        {
            x[p] = mer(x[p], d), tg[p] = mer(tg[p], d);
            return;
        }
        pushdown(p);
        int cm = cl + cr >> 1;
        if (l <= cm) assign_max(p << 1, cl, cm, l, r, d);
        if (r > cm) assign_max(p << 1 | 1, cm + 1, cr, l, r, d);
        x[p] = mer(x[p << 1], x[p << 1 | 1]);
    }
} sgt;

int pre[N];
Data f[N];

struct SegTree2
{
    int x[N << 2];

    void init(int p, int cl, int cr)
    {
        if (cl == cr) return x[p] = cl, void();
        int cm = cl + cr >> 1;
        init(p << 1, cl, cm);
        init(p << 1 | 1, cm + 1, cr);
        if (c[x[p << 1]] > c[x[p << 1 | 1]]) x[p] = x[p << 1];
        else x[p] = x[p << 1 | 1];
    }

    int get_max(int p, int cl, int cr, int l, int r)
    {
        if (cl >= l && cr <= r) return x[p];
        int cm = cl + cr >> 1;
        if (l <= cm && r > cm)
        {
            int a = get_max(p << 1, cl, cm, l, r),
                b = get_max(p << 1 | 1, cm + 1, cr, l, r);
            return c[a] > c[b] ? a : b;
        }
        else if (l <= cm) return get_max(p << 1, cl, cm, l, r);
        else return get_max(p << 1 | 1, cm + 1, cr, l, r);
    }
} sgt2;

void solve(int l, int r)
{
    if (l == r)
    {
        Data t = f[l];
        f[l] = mer(f[l], sgt.get_max(1, 0, n, l, l));
        sgt.assign_max(1, 0, n, l, l, t);
        return;
    }

    int mid = sgt2.get_max(1, 1, n, l + 1, r) - 1, mxc = c[mid + 1];

    solve(l, mid);

    int p = max(mid + 1, l + mxc);
    Data cur_x = {INT_MIN, 0};
    while (p <= r && p - mxc < mid && pre[p] <= l)
    {
        if (cur_x.mx == INT_MIN) cur_x = sgt.get_max(1, 0, n, l, p - mxc);
        else cur_x = mer(cur_x, f[p - mxc]);
        Data x = cur_x; ++x.mx;
        f[p] = mer(f[p], x);
        ++p;
    }
    if (p > r) goto SOLVE_R;

    if (pre[p] <= l)
    {
        int cl = p, cr = r, ca = p;
        while (cl <= cr)
        {
            int cm = cl + cr >> 1;
            if (pre[cm] <= l) ca = cm, cl = cm + 1;
            else cr = cm - 1;
        }
        Data x = sgt.get_max(1, 0, n, l, mid); ++x.mx;
        sgt.assign_max(1, 0, n, p, ca, x);
        p = ca + 1;
    }
    if (p > r) goto SOLVE_R;

    while (p <= r && pre[p] <= mid)
    {
        Data x = sgt.get_max(1, 0, n, pre[p], min(mid, p - mxc));
        ++x.mx;
        f[p] = mer(f[p], x);
        ++p;
    }

    SOLVE_R: solve(mid + 1, r);
}

struct SegTree3
{
    int x[N << 2];

    void init(int p, int cl, int cr)
    {
        if (cl == cr) return x[p] = d[cl], void();
        int cm = cl + cr >> 1;
        init(p << 1, cl, cm);
        init(p << 1 | 1, cm + 1, cr);
        x[p] = min(x[p << 1], x[p << 1 | 1]);
    }

    int get_min(int p, int cl, int cr, int l, int r)
    {
        if (cl >= l && cr <= r) return x[p];
        int cm = cl + cr >> 1;
        if (l <= cm && r > cm)
        {
            return min(get_min(p << 1, cl, cm, l, r),
                get_min(p << 1 | 1, cm + 1, cr, l, r));
        }
        else if (l <= cm) return get_min(p << 1, cl, cm, l, r);
        else return get_min(p << 1 | 1, cm + 1, cr, l, r);
    }
} sgt3;

signed main(void)
{
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    ios::sync_with_stdio(0), cin.tie(nullptr);

    cin >> n;
    F(i, 1, n) cin >> c[i] >> d[i];

    sgt3.init(1, 1, n);
    pre[1] = 0;
    F(i, 2, n)
    {
        pre[i] = pre[i - 1];
        while (sgt3.get_min(1, 1, n, pre[i] + 1, i) < i - pre[i]) ++pre[i];
        // cout << i << ": " << pre[i] << '\n';
    }

    f[0] = {0, 1};
    F(i, 1, n) f[i] = {-n, 0};
    sgt.init(1, 0, n);

    sgt2.init(1, 1, n);
    solve(0, n);

    // F(i, 0, n) cout << i << ": " << f[i].mx << ' ' << f[i].s << '\n';

    if (f[n].s == 0) cout << "NIE" << endl;
    else cout << f[n].mx << ' '  << f[n].s << endl;

    return 0;
}