Shared code

#include "bits/stdc++.h"
using namespace std;

constexpr int MOD = 1e9 + 7;

void update(vector<int>& bit, int index, const int delta) {
    const int n = (int)bit.size();
    for (; index < n; index += index & -index)
        (bit[index] += delta) %= MOD;
}

int query(const vector<int>& bit, int index) {
    int sum = 0;
    for (; index > 0; index -= index & -index)
        (sum += bit[index]) %= MOD;
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    vector<int> idx(n), rank(n, 1);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j) {return a[i] < a[j];});
    int m = 1;
    for (int i = 1; i < n; i++)
        rank[idx[i]] = m += (a[idx[i]] != a[idx[i - 1]]);
    vector<int> bit(m + 1);
    for (const auto& r : rank)
        update(bit, r, query(bit, r - 1) + 1);
    cout << query(bit, m) << '\n';
}