GROWING UP IS HARD TO DO

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
using ll = long long;

constexpr int N = 3e5 + 5;
constexpr ll mod = 1e9 + 7;
constexpr int Inf = 1e9 + 7;

int n, a[N];
ll dp[N], f[N];

vector<int> b[N];
vector<ll> sum[N];

void Read()
{
    cin >> n;

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

void Solve()
{
    a[n + 1] = Inf;

    b[0].emplace_back(0);
    sum[0].emplace_back(dp[0] = 1);

    for (int i = 1; i <= n; ++i)
    {
        b[i].emplace_back(n + 1);
        sum[i].emplace_back(0);
    }

    int ans(0);

    for (int i = 1; i <= n; ++i)
    {
        b[n + 1].clear();
        b[n + 1].emplace_back(i);
        // Calculate longgest increasing subsequence
        int j = lower_bound(b + 1, b + n + 1, b[n + 1], [&](const vector<int> &u, const vector<int> &v)
                            { return a[u.back()] < a[v.back()]; }) -
                b;

        // Calculate dp
        if (j == 1)
            dp[i] = 1;
        else
        {
            int l = lower_bound(b[j - 1].begin(), b[j - 1].end(), i, [&](const int &x, const int &y)
                                { return a[x] > a[y] || (a[x] == a[y] && x < y); }) -
                    b[j - 1].begin();

            dp[i] = (sum[j - 1].back() - sum[j - 1][l - 1]) % mod; // sum[j - 1][l - 1] == sum[j - 1][h]
        }

        if (a[b[j].back()] == a[i])
            f[i] = (dp[i] - dp[b[j].back()]) % mod;
        else
            f[i] = dp[i];

        ans = max(ans, j);

        b[j].emplace_back(i);
        sum[j].emplace_back((sum[j].back() + f[i]) % mod);
    }

    cout << (sum[ans].back() + mod) % mod;
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Read();
    Solve();
}