Problem Description
As to a permutation p1,p2,⋯,pn from 1 to n, it is uncomplicated for each 1≤i≤n to calculate (li,ri) meeting the condition that min(pL,pL+1,⋯,pR)=pi if and only if li≤L≤i≤R≤ri for each 1≤L≤R≤n.

Given the positive integers n, (li,ri) (1≤i≤n), you are asked to calculate the number of possible permutations p1,p2,⋯,pn from 1 to n, meeting the above condition.

The answer may be very large, so you only need to give the value of answer modulo 109+7.

Input
The input contains multiple test cases.

For each test case:

The first line contains one positive integer n, satisfying 1≤n≤106.

The second line contains n positive integers l1,l2,⋯,ln, satisfying 1≤li≤i for each 1≤i≤n.

The third line contains n positive integers r1,r2,⋯,rn, satisfying i≤ri≤n for each 1≤i≤n.

It’s guaranteed that the sum of n in all test cases is not larger than 3⋅106.

Warm Tips for C/C++: input data is so large (about 38 MiB) that we recommend to use fread() for buffering friendly.

size_t fread(void *buffer, size_t size, size_t count, FILE *stream); // reads an array of count elements, each one with a size of size bytes, from the stream and stores them in the block of memory specified by buffer; the total number of elements successfully read is returned.

Output
For each test case, output “Case #x: y” in one line (without quotes), where x indicates the case number starting from 1 and y denotes the answer of corresponding case.

Sample Input

3
1 1 3
1 3 3
5
1 2 2 4 5
5 2 5 5 5

Sample Output

Case #1: 2
Case #2: 3

解法：

按照题解的原理，直接用map映射之后DFS即可，完全不用笛卡尔树（压根不知道笛卡尔树是个啥。。）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1000010;
const int mod = 1e9+7;
typedef pair <int,int> PI;
map <PI, int> mp;
struct FastIO
{
    static const int S = 1310720;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar()
    {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) exit(0);
        return buf[pos ++];
    }
    inline int xuint()
    {
        int c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x;
    }
    inline int xint()
    {
        int s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline void xstring(char *s)
    {
        int c = xchar();
        while (c <= 32) c = xchar();
        for (; c > 32; c = xchar()) * s++ = c;
        *s = 0;
    }
    inline void wchar(int x)
    {
        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos ++] = x;
    }
    inline void wint(LL x)
    {
        if (x < 0) wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n ++] = '0' + x % 10, x /= 10;
        while (n--) wchar(s[n]);
    }
    inline void wstring(const char *s)
    {
        while (*s) wchar(*s++);
    }
    ~FastIO()
    {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;
int n;
LL ans;
int l[maxn], r[maxn];
LL fac[maxn], inv[maxn];
void init()
{
    inv[0] = fac[0] = 1LL;
    inv[1] = 1;
    for(int i=1; i<maxn; i++)
    {
        fac[i] = fac[i-1]*i%mod;
    }
    for(int i=2; i<maxn; i++)
    {
        inv[i] = (mod - mod/i)*inv[mod%i]%mod;
    }
    inv[0] = 1;
    for(int i=1; i<maxn; i++){
        inv[i] = inv[i-1]*inv[i]%mod;
    }
}
LL C(int n, int m){
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void dfs(int L, int R)
{
    if(L>R) return;
    if(ans == 0) return;
    int x = mp[make_pair(L,R)];
    if(x == 0)
    {
        ans = 0;
        return ;
    }
    int Len = R-L;
    int len = x-L;
    ans = ans * C(Len, len) % mod;
    dfs(L, x-1);
    dfs(x+1, R);
}
int main()
{
    int ks = 0;
    init();
    while(1)
    {
        n = io.xint();
        mp.clear();
        for(int i=1; i<=n; i++) l[i] = io.xint();
        for(int i=1; i<=n; i++) r[i] = io.xint();
        for(int i=1; i<=n; i++)
        {
            mp[make_pair(l[i], r[i])] = i;
        }
        ans = 1LL;
        dfs(1, n);
        //printf("Case #%d: %lld\n", ++ks, ans);
        io.wstring("Case #");
        io.wint(++ks);
        io.wstring(": ");
        io.wint(ans);
        io.wchar('\n');
    }
    return 0;
}