LINEUP.cpp

#define task "LINEUP"
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 3e6 + 5;
constexpr ll mod = 1e9 + 7;
int n, a[N];
ll f[N], g[N];

void Read()
{
    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];
}

void Sub_1()
{
    f[n + 1] = 1;

    for (int i = n; i; --i)
        for (int j = i + 1; j <= n + 1; ++j)
        {
            for (int t = i + 1; t < j; ++t)
                if (a[i] < a[t])
                    goto done;

            (f[i] += f[j]) %= mod;
        done:;
        }

    cout << f[1];
}

void Sub_2()
{
    f[n + 1] = 1;

    for (int i = n, j; i; --i)
    {
        j = i;
        while (j <= n && a[j] <= a[i])
            (f[i] += f[++j]) %= mod;
    }

    cout << f[1];
}

void Sub_4()
{
    vector<int> s;
    f[n + 1] = g[n + 1] = 1;

    for (int i = n; i; --i)
    {
        while (!s.empty() && a[s.back()] <= a[i])
            s.pop_back();

        f[i] = (g[i + 1] - (s.empty() ? 0 : g[s.back() + 1])) % mod;

        s.emplace_back(i);

        g[i] = (g[i + 1] + f[i]) % mod;
    }

    cout << (f[1] + mod) % mod;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();
    if (n <= 300)
        Sub_1();
    else if (n <= 3000)
        Sub_2();
    else
        Sub_4();
}