#include #include #include using namespace std; using mint = atcoder::modint1000000007; using ll = long long; using S = pair; S op(S a, S b) { if(a.first == b.first) return S{a.first, a.second + b.second}; if(a.first < b.first) swap(a, b); return S{a.first, a.second}; } S e() { return S{-1, 0}; } int opmax(int a, int b) { return max(a, b); } int emax() { return 0; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int N; cin >> N; vector A(N); for(int i = 0; i < N; i++) cin >> A[i]; vector cc = A; sort(cc.begin(), cc.end()); cc.erase(unique(cc.begin(), cc.end()), cc.end()); for(int i = 0; i < N; i++) A[i] = (lower_bound(cc.begin(), cc.end(), A[i]) - cc.begin()) + 1; atcoder::segtree ep(N + 2); atcoder::segtree dp(N + 1); vector> B(N + 1); for(int i = 0; i < N; i++) B[A[i]].push_back(i); ep.set(0, {0, 1}); for(int it = 1; it <= N; it++) if(!B[it].empty()) { const int sz = B[it].size(); for(int j = sz - 1; j >= 0; j--) { int i = B[it][j] + 1; dp.set(i, dp.prod(0, i) + 1); ep.set(i, {dp.get(i), ep.prod(0, i).second}); } } int MAX = dp.all_prod(); mint ans = 0; for(int i = 1; i <= N; i++) if(dp.get(i) == MAX) ans += ep.get(i).second; cout << ans.val() << "\n"; }