Growing Up is Hard to Do

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#define task "Growing Up is Hard to Do"
#define bit(i, x) (((x) >> (i)) & 1)

using namespace std;
using ll = long long;

const int N = 3e5 + 2;
const int mod = 1e9 + 7;
struct Trie
{
    Trie *child[2];
    ll v;
    Trie()
    {
        child[0] = child[1] = NULL;
        v = 0;
    }
};

void Add(Trie *a, int v, ll amount)
{
    int id = 18;
    while (1)
    {
        if (id == -1)
        {
            (a->v += amount) %= mod;
            return;
        }
        if (!(a->child[bit(id, v)]))
            a->child[bit(id, v)] = new Trie;
        (a->v += amount) %= mod;
        a = a->child[bit(id, v)];
        --id;
    }
}

ll Get(Trie *a, int x)
{
    int id = 18;
    ll ans(0);
    while (1)
    {
        if (id == -1)
        {
            (ans += a->v) %= mod;
            break;
        }
        if (bit(id, x))
        {
            if (a->child[0])
                (ans += a->child[0]->v) %= mod;
            if (a->child[1])
                a = a->child[1];
            else
                break;
        }
        else
        {
            if (a->child[0])
                a = a->child[0];
            else
                break;
        }
        --id;
    }
    return ans;
}

int n, id[N], m;
int a[N];
map<int, int> ck[N];
vector<int> endof(N);
vector<Trie> d(N);
ll dp[N];

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

void Compress()
{
    sort(id + 1, id + n + 1, [&](const int &x, const int &y) {
        return a[x] < a[y];
    });
    int l(0);
    for (int i = 1; i <= n; ++i)
    {
        ++l;
        int j = i;
        while (j <= n && a[id[i]] == a[id[j]])
            ++j;
        while (i < j)
            a[id[i++]] = l;
        --i;
    }
}

void Solve()
{
    fill(endof.begin(), endof.end(), mod);
    endof[0] = 0;
    Add(&d[0], 0, 1);
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        int j = lower_bound(endof.begin(), endof.end(), a[i]) - endof.begin();
        if (ck[a[i]][j])
            continue;
        ck[a[i]][j] = 1;
        ll now = Get(&d[j - 1], a[i] - 1);
        dp[j] = (dp[j] + now) % mod;
        Add(&d[j], a[i], now);
        endof[j] = min(endof[j], a[i]);
        ans = max(ans, j);
    }
    cout << dp[ans];
}

int32_t main()
{
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Read();
    Compress();
    Solve();
}