#995341 (C++23) No.992 最長増加部分列の数え上げ

提出ソース
結果

問題	No.992 最長増加部分列の数え上げ
ユーザー	miscalc
提出日時	2024-07-16 20:44:45
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	42 ms / 2,000 ms
コード長	19,022 bytes
コンパイル時間	3,833 ms
コンパイル使用メモリ	278,864 KB
実行使用メモリ	7,524 KB
最終ジャッジ日時	2024-07-16 20:44:54
合計ジャッジ時間	7,195 ms
ジャッジサーバーID （参考情報）	judge5 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	16 ms 6,944 KB
testcase_05	AC	13 ms 6,940 KB
testcase_06	AC	20 ms 6,944 KB
testcase_07	AC	15 ms 6,940 KB
testcase_08	AC	9 ms 6,940 KB
testcase_09	AC	15 ms 6,944 KB
testcase_10	AC	21 ms 6,940 KB
testcase_11	AC	25 ms 6,940 KB
testcase_12	AC	6 ms 6,940 KB
testcase_13	AC	15 ms 6,940 KB
testcase_14	AC	15 ms 6,944 KB
testcase_15	AC	7 ms 6,940 KB
testcase_16	AC	36 ms 6,940 KB
testcase_17	AC	9 ms 6,940 KB
testcase_18	AC	14 ms 6,944 KB
testcase_19	AC	25 ms 6,940 KB
testcase_20	AC	39 ms 6,944 KB
testcase_21	AC	41 ms 6,944 KB
testcase_22	AC	41 ms 6,940 KB
testcase_23	AC	40 ms 6,944 KB
testcase_24	AC	39 ms 6,944 KB
testcase_25	AC	41 ms 6,944 KB
testcase_26	AC	41 ms 6,944 KB
testcase_27	AC	40 ms 6,944 KB
testcase_28	AC	41 ms 6,944 KB
testcase_29	AC	42 ms 6,940 KB
testcase_30	AC	37 ms 7,180 KB
testcase_31	AC	37 ms 7,420 KB
testcase_32	AC	38 ms 7,376 KB
testcase_33	AC	37 ms 7,524 KB
testcase_34	AC	38 ms 7,392 KB
testcase_35	AC	32 ms 7,312 KB
testcase_36	AC	32 ms 7,184 KB
testcase_37	AC	32 ms 7,184 KB
testcase_38	AC	32 ms 7,312 KB
testcase_39	AC	32 ms 7,316 KB
testcase_40	AC	37 ms 7,060 KB
testcase_41	AC	37 ms 7,064 KB
testcase_42	AC	37 ms 7,056 KB
testcase_43	AC	37 ms 6,940 KB
testcase_44	AC	37 ms 6,944 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;

#include <tr2/dynamic_bitset>
using dbs = tr2::dynamic_bitset<>;

//*
#define INCLUDE_MODINT
//*/
#ifdef INCLUDE_MODINT
#include <atcoder/modint>
using namespace atcoder;
// using mint = modint998244353;
using mint = modint1000000007;
// using mint = modint;
#endif

namespace mytemplate
{
  using ll = long long;
  using dbl = double;
  using ld = long double;
  using uint = unsigned int;
  using ull = unsigned long long;
  using pll = pair<ll, ll>;
  using tlll = tuple<ll, ll, ll>;
  using tllll = tuple<ll, ll, ll, ll>;
  using vl = vector<ll>;
  using vpll = vector<pll>;
  using vtlll = vector<tlll>;
  using vtllll = vector<tllll>;
  using vstr = vector<string>;
  using vvl = vector<vector<ll>>;
  #ifdef __SIZEOF_INT128__
    using i128 = __int128_t;
    i128 stoi128(string s) { i128 res = 0; if (s.front() == '-') { for (int i = 1; i < (int)s.size(); i++) res = 10 * res + s[i] - '0'; res = -res; } else { for (auto c : s) res = 10 * res + c - '0'; } return res; }
    string i128tos(i128 x) { string sign = "", res = ""; if (x < 0) x = -x, sign = "-"; while (x > 0) { res += '0' + x % 10; x /= 10; } reverse(res.begin(), res.end()); if (res == "") return "0"; return sign + res; }
    istream &operator>>(istream &is, i128 &a) { string s; is >> s; a = stoi128(s); return is; }
    ostream &operator<<(ostream &os, const i128 &a) { os << i128tos(a); return os; }
  #endif

  #define overload4(_1, _2, _3, _4, name, ...) name
  #define rep1(i, n) for (ll i = 0; i < ll(n); i++)
  #define rep2(i, l, r) for (ll i = ll(l); i < ll(r); i++)
  #define rep3(i, l, r, d) for (ll i = ll(l); (d) > 0 ? i < ll(r) : i > ll(r); i += d)
  #define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
  #define ALL(a) (a).begin(), (a).end()

  const ll INF = 4'000'000'000'000'000'037;

  bool chmin(auto &a, const auto &b) { return a > b ? a = b, true : false; }
  bool chmax(auto &a, const auto &b) { return a < b ? a = b, true : false; }
  template <class T1 = ll> T1 safemod(auto a, auto m) { T1 res = a % m; if (res < 0) res += m; return res; }
  template <class T1 = ll> T1 divfloor(auto a, auto b) { if (b < 0) a = -a, b = -b; return (a - safemod(a, b)) / b; }
  template <class T1 = ll> T1 divceil(auto a, auto b) { if (b < 0) a = -a, b = -b; return divfloor(a + b - 1, b); }
  template <class T1 = ll> T1 pow_ll(auto a, auto b) { if (a == 0) return b == 0 ? 1 : 0; if (a == 1) return a; if (a == -1) return b & 1 ? -1 : 1; ll res = 1; rep(_, b) res *= a; return res; }
  template <class T1 = ll> T1 mul_limited(auto a, auto b, T1 m = INF) { return b == 0 ? 0 : a > m / b ? m : a * b; }
  template <class T1 = ll> T1 pow_limited(auto a, auto b, T1 m = INF) { if (a == 0) return b == 0 ? 1 : 0; if (a == 1) return a; ll res = 1; rep(_, b) { if (res > m / a) return m; res *= a; } return res; }
  template <class T1 = ll> vector<T1> b_ary(T1 x, int b) { vector<T1> a; while (x > 0) { a.emplace_back(x % b); x /= b; } reverse(a.begin(), a.end()); return a; }
  template <class T1 = ll> vector<T1> b_ary(T1 x, int b, int n) { vector<T1> a(n); rep(i, n) { a[i] = x % b; x /= b; } reverse(a.begin(), a.end()); return a; }
  template <class T1 = ll> string b_ary_str(T1 x, int b) { auto a = b_ary(x, b); string s = ""; for (auto &&ai : a) s += (ai < 10 ? '0' + ai : 'A' + (ai - 10)); return s; }
  template <class T1 = ll> string b_ary_str(T1 x, int b, int n) { auto a = b_ary(x, b, n); string s = ""; for (auto &&ai : a) s += (ai < 10 ? '0' + ai : 'A' + (ai - 10)); return s; }
  template <class T>
  vector<vector<T>> iprod(const vector<T> &a)
  {
    vector<vector<T>> res;
    vector<T> tmp(a.size());
    auto dfs = [&](auto self, int i)
    {
      if (i == (int)a.size())
      {
        res.emplace_back(tmp);
        return;
      }
      rep(j, a[i])
      {
        tmp[i] = j;
        self(self, i + 1);
      }
    };
    dfs(dfs, 0);
    return res;
  }

  template <class T = ll> struct max_op { T operator()(const T &a, const T &b) const { return max(a, b); } };
  template <class T = ll> struct min_op { T operator()(const T &a, const T &b) const { return min(a, b); } };
  template <class T, const T val> struct const_fn { T operator()() const { return val; } };
  using max_e = const_fn<ll, -INF>;
  using min_e = const_fn<ll, INF>;
  using zero_fn = const_fn<ll, 0LL>;

  template <class T = ll> vector<T> digitvec(const string &s) { int n = s.size(); vector<T> a(n); rep(i, n) a[i] = s[i] - '0'; return a; }
  template <class T, size_t d, size_t i = 0> auto make_vec(const auto (&sz)[d], const T &init) { if constexpr (i < d) return vector(sz[i], make_vec<T, d, i + 1>(sz, init)); else return init; }
  template <class T = ll> vector<T> permid(int n, int base_index = 0) { vector<T> p(n); rep(i, n) p[i] = i + base_index; return p; }
  template <class T = ll> vector<T> perminv(const vector<T> &p) { vector<T> q(p.size()); rep(i, p.size()) q[p[i]] = i; return q; }
  template <class T = ll> vector<T> combid(int n, int k) { vector<T> p(n, 0); fill(p.rbegin(), p.rbegin() + k, 1); return p; }
  template <class F> auto gen_vec(int n, const F &f) { using T = decltype(f(0)); vector<T> res(n); rep(i, n) res[i] = f(i); return res; }
  // res[i] = op[0, i) for 0 <= i < n+1
  template <class T, class F = decltype(plus<>())> vector<T> cuml(vector<T> v, const F &op = plus<>(), const T &e = 0) { v.emplace_back(e); exclusive_scan(v.begin(), v.end(), v.begin(), e, op); return v; }
  // res[i] = op[i, n) for 0 <= i < n+1
  template <class T, class F = decltype(plus<>())> vector<T> cumr(vector<T> v, const F &op = plus<>(), const T &e = 0) { v.insert(v.begin(), e); exclusive_scan(v.rbegin(), v.rend(), v.rbegin(), e, op); return v; }
  // res[i] = v[i] - v[i-1] for 0 <= i < n+1
  template <class T> vector<T> adjd(vector<T> v) { v.emplace_back(0); adjacent_difference(v.begin(), v.end(), v.begin()); return v; }
  template <class T> vector<T> cumlmax(const vector<T> &v) { return cuml(v, max_op<T>(), max_e()()); }
  template <class T> vector<T> cumrmax(const vector<T> &v) { return cumr(v, max_op<T>(), max_e()()); }
  template <class T> vector<T> cumlmin(const vector<T> &v) { return cuml(v, min_op<T>(), min_e()()); }
  template <class T> vector<T> cumrmin(const vector<T> &v) { return cumr(v, min_op<T>(), min_e()()); }
  template <class T> vector<T> sorted(vector<T> v) { sort(v.begin(), v.end()); return v; }
  template <class T> vector<T> reversed(const vector<T> &v) { return {v.rbegin(), v.rend()}; }
  template <class T> void unique(vector<T> &v) { v.erase(unique(v.begin(), v.end()), v.end()); }
  template <class T> vector<T> uniqued(vector<T> v) { v.erase(unique(v.begin(), v.end()), v.end()); return v; }
  template <class T> void sortunique(vector<T> &v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); }
  template <class T> vector<T> sortuniqued(vector<T> v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); return v; }
  template <class T> void rotate(vector<T> &v, int k) { rotate(v.begin(), v.begin() + k, v.end()); }
  template <class T> vector<T> rotated(vector<T> v, int k) { rotate(v.begin(), v.begin() + k, v.end()); return v; }
  string sorted(string s) { sort(s.begin(), s.end()); return s; }
  string reversed(const string &s) { return {s.rbegin(), s.rend()}; }
  void unique(string &s) { s.erase(unique(s.begin(), s.end()), s.end()); }
  string uniqued(string s) { s.erase(unique(s.begin(), s.end()), s.end()); return s; }
  void sortunique(string &s) { sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end()); }
  string sortuniqued(string s) { sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end()); return s; }
  void rotate(string &s, int k) { rotate(s.begin(), s.begin() + k, s.end()); }
  string rotated(string s, int k) { rotate(s.begin(), s.begin() + k, s.end()); return s; }
  template <class T> vector<vector<T>> top(const vector<vector<T>> &a) { if (a.empty()) return {}; const size_t n = a.size(), m = a[0].size(); vector<vector<T>> b(m, vector<T>(n)); for (size_t i = 0; i < n; i++) for (size_t j = 0; j < m; j++) b[j][i] = a[i].at(j); return b; }
  vstr top(const vstr &a) { if (a.empty()) return {}; const size_t n = a.size(), m = a[0].size(); vstr b(m, string(n, 0)); for (size_t i = 0; i < n; i++) for (size_t j = 0; j < m; j++) b[j][i] = a[i].at(j); return b; }
  template <class T> vector<vector<T>> rot90(const vector<vector<T>> &a) { if (a.empty()) return {}; const size_t n = a.size(), m = a[0].size(); vector<vector<T>> b(m, vector<T>(n)); for (size_t i = 0; i < n; i++) for (size_t j = 0; j < m; j++) b[j][n - 1 - i] = a[i][j]; return b; }
  vstr rot90(const vstr &a) { if (a.empty()) return {}; const size_t n = a.size(), m = a[0].size(); vstr b(m, string(n, 0)); for (size_t i = 0; i < n; i++) for (size_t j = 0; j < m; j++) b[j][n - 1 - i] = a[i][j]; return b; }

  #if __cplusplus < 202002L
    ull bit_ceil(ull x) { ull y = 1; while (y < x) y <<= 1; return y; }
    ull bit_floor(ull x) { ull y = 1; while (y <= x) y <<= 1; return y >> 1; }
    ull bit_width(ull x) { ull y = 1, z = 0; while (y <= x) y <<= 1, z++; return z; }
    ull countr_zero(ull x) { return __builtin_ctzll(x); }
    ull popcount(ull x) { return __builtin_popcountll(x); }
    ull has_single_bit(ull x) { return popcount(x) == 1; }
  #endif
  ull lsb_pos(ull x) { assert(x != 0); return countr_zero(x); }
  ull msb_pos(ull x) { assert(x != 0); return bit_width(x) - 1; }
  ull lsb_mask(ull x) { assert(x != 0); return x & -x; }
  ull msb_mask(ull x) { assert(x != 0); return bit_floor(x); }
  bool btest(ull x, uint k) { return (x >> k) & 1; }
  template <class T> void bset(T &x, uint k, bool b = 1) { b ? x |= (1ULL << k) : x &= ~(1ULL << k); }
  template <class T> void bflip(T &x, uint k) { x ^= (1ULL << k); }
  bool bsubset(ull x, ull y) { return (x & y) == x; }
  template <class T> vector<pair<T, T>> bsubsets(T x) { vector<pair<T, T>> res; for (T y = x; y > 0; y = (y - 1) & x) res.emplace_back(make_pair(y, x & ~y)); res.emplace_back(make_pair(0, x)); return res; }

  template <class Tuple, size_t... I> Tuple tuple_add(Tuple &a, const Tuple &b, const index_sequence<I...>) { ((get<I>(a) += get<I>(b)), ...); return a; }
  template <class Tuple> Tuple operator+=(Tuple &a, const Tuple &b) { return tuple_add(a, b, make_index_sequence<tuple_size_v<Tuple>>{}); }
  template <class Tuple> Tuple operator+(Tuple a, const Tuple &b) { return a += b; }
  template <class T, class U> void offset(vector<T> &v, U add) { for (auto &vi : v) vi += add; }
  template <class T, class U> void offset(vector<vector<T>> &v, U add) { for (auto &vi : v) for (auto &vij : vi) vij += add; }
  template <class T, const size_t m> array<vector<T>, m> top(const vector<array<T, m>> &a) { const size_t n = a.size(); array<vector<T>, m> b; b.fill(vector<T>(n)); for (size_t i = 0; i < n; i++) for (size_t j = 0; j < m; j++) b[j][i] = a[i][j]; return b; }
  template <class T, const size_t n> vector<array<T, n>> top(const array<vector<T>, n> &a) { if (a.empty()) return {}; const size_t m = a[0].size(); vector<array<T, n>> b(m); for (size_t i = 0; i < n; i++) for (size_t j = 0; j < m; j++) b[j][i] = a[i].at(j); return b; }
  template <class T, class U> pair<vector<T>, vector<U>> top(const vector<pair<T, U>> &a) { const size_t n = a.size(); vector<T> b(n); vector<U> c(n); for (size_t i = 0; i < n; i++) tie(b[i], c[i]) = a[i]; return make_pair(b, c); }
  template <class T, class U> vector<pair<T, U>> top(const pair<vector<T>, vector<U>> &a) { const size_t n = a.first.size(); vector<pair<T, U>> b(n); for (size_t i = 0; i < n; i++) b[i] = make_pair(a.first[i], a.second.at(i)); return b; }
  template <class T1, class T2, class T3> tuple<vector<T1>, vector<T2>, vector<T3>> top(const vector<tuple<T1, T2, T3>> &a) { const size_t n = a.size(); vector<T1> b(n); vector<T2> c(n); vector<T3> d(n); for (size_t i = 0; i < n; i++) tie(b[i], c[i], d[i]) = a[i]; return make_tuple(b, c, d); }
  template <class T1, class T2, class T3> vector<tuple<T1, T2, T3>> top(const tuple<vector<T1>, vector<T2>, vector<T3>> &a) { const size_t n = get<0>(a).size(); vector<tuple<T1, T2, T3>> b(n); for (size_t i = 0; i < n; i++) b[i] = make_tuple(get<0>(a)[i], get<1>(a).at(i), get<2>(a).at(i)); return b; }
  template <class T1, class T2, class T3, class T4> tuple<vector<T1>, vector<T2>, vector<T3>, vector<T4>> top(const vector<tuple<T1, T2, T3, T4>> &a) { const size_t n = a.size(); vector<T1> b(n); vector<T2> c(n); vector<T3> d(n); vector<T4> e(n); for (size_t i = 0; i < n; i++) tie(b[i], c[i], d[i], e[i]) = a[i]; return make_tuple(b, c, d, e); }
  template <class T1, class T2, class T3, class T4> vector<tuple<T1, T2, T3, T4>> top(const tuple<vector<T1>, vector<T2>, vector<T3>, vector<T4>> &a) { const size_t n = get<0>(a).size(); vector<tuple<T1, T2, T3, T4>> b(n); for (size_t i = 0; i < n; i++) b[i] = make_tuple(get<0>(a)[i], get<1>(a).at(i), get<2>(a).at(i), get<3>(a).at(i)); return b; }

  #ifdef INCLUDE_MODINT
    using namespace atcoder;
    template <class T, internal::is_modint_t<T> * = nullptr> istream &operator>>(istream &is, T &a) { ll v; is >> v; a = v; return is; }
    template <class T, internal::is_modint_t<T> * = nullptr> ostream &operator<<(ostream &os, const T &a) { os << a.val(); return os; }
    #define MINT(...) mint __VA_ARGS__; INPUT(__VA_ARGS__)
  #endif
  
  template <class Tuple, enable_if_t<__is_tuple_like<Tuple>::value == true> * = nullptr> istream &operator>>(istream &is, Tuple &t) { apply([&](auto&... a){ (is >> ... >> a); }, t); return is; }
  template <class... T> void INPUT(T&... a) { (cin >> ... >> a); }
  template <class T> void INPUTVEC(int n, vector<T> &v) { v.resize(n); rep(i, n) cin >> v[i]; }
  template <class T, class... Ts> void INPUTVEC(int n, vector<T>& v, vector<Ts>&... vs) { INPUTVEC(n, v); INPUTVEC(n, vs...); }
  template <class T> void INPUTVEC2(int n, int m, vector<vector<T>> &v) { v.assign(n, vector<T>(m)); rep(i, n) rep(j, m) cin >> v[i][j]; }
  template <class T, class... Ts> void INPUTVEC2(int n, int m, vector<T>& v, vector<Ts>&... vs) { INPUTVEC2(n, m, v); INPUTVEC2(n, m, vs...); }
  #define INT(...) int __VA_ARGS__; INPUT(__VA_ARGS__)
  #define LL(...) ll __VA_ARGS__; INPUT(__VA_ARGS__)
  #define STR(...) string __VA_ARGS__; INPUT(__VA_ARGS__)
  #define ARR(T, n, ...) array<T, n> __VA_ARGS__; INPUT(__VA_ARGS__)
  #define VEC(T, n, ...) vector<T> __VA_ARGS__; INPUTVEC(n, __VA_ARGS__)
  #define VEC2(T, n, m, ...) vector<vector<T>> __VA_ARGS__; INPUTVEC2(n, m, __VA_ARGS__)
  template <class T> void PRINT(const T &a) { cout << a << '\n'; }
  template <class T, class... Ts> void PRINT(const T& a, const Ts&... b) { cout << a; (cout << ... << (cout << ' ', b)); cout << '\n'; }
  template <class T> void PRINTVEC(const vector<T> &v) { int n = v.size(); rep(i, n) cout << v[i] << (i == n - 1 ? "" : " "); cout << '\n'; }
  template <class T> void PRINTVECT(const vector<T> &v) { for (auto &vi : v) cout << vi << '\n';}
  template <class T> void PRINTVEC2(const vector<vector<T>> &v) { for (auto &vi : v) PRINTVEC(vi); }
  #define PRINTEXIT(...) do { PRINT(__VA_ARGS__); exit(0); } while (false)
  #define PRINTRETURN(...) do { PRINT(__VA_ARGS__); return; } while (false)

  #ifdef LOCAL // ttps://zenn.dev/sassan/articles/19db660e4da0a4
    #include "/Users/Shared/cpp-dump-main/dump.hpp"
    #define dump(...) cpp_dump(__VA_ARGS__)
    CPP_DUMP_DEFINE_EXPORT_OBJECT(mint, val());
    #ifdef INCLUDE_MODINT
      CPP_DUMP_DEFINE_DANGEROUS_EXPORT_OBJECT(val());
    #endif
  #else
    #define dump(...)
  #endif
}
using namespace mytemplate;

// idx[i] := A の i 番目が LIS に使われる可能性があるなら、どの添字で使われるか
//           使われる可能性がないなら -1
// cand[j] := LIS の j 番目になりうる A の要素の添字の配列 (昇順)
// 特に、cand[j].front() たちをとってきたものが辞書順最小の LIS,
// cand[j].back() たちをとってきたものが辞書順最大の LIS
struct LongestIncreasingSubsequence
{
  vector<int> idx;
  vector<vector<int>> cand;
  LongestIncreasingSubsequence() {}
  template <class T>
  LongestIncreasingSubsequence(const vector<T> &a) : idx(a.size())
  {
    const int n = a.size();
    vector<T> dp;
    for (int i = 0; i < n; i++)
    {
      auto it = lower_bound(dp.begin(), dp.end(), a[i]);
      idx[i] = it - dp.begin();
      if (it == dp.end())
        dp.emplace_back(a[i]);
      else
        *it = a[i];
    }

    const int len = dp.size();
    cand.resize(len);
    dump(idx);
    for (int i = n - 1, j = len - 1; i >= 0; i--)
    {
      if (idx[i] == j)
        cand[j--].emplace_back(i);
      else if (idx[i] + 1 == len || (!cand[idx[i] + 1].empty() && a[i] < a[cand[idx[i] + 1].back()]))
        cand[idx[i]].emplace_back(i);
      else
        idx[i] = -1;
    }
    for (auto &candj : cand)
      reverse(candj.begin(), candj.end());
  }
};

void main2()
{
  /* https://judge.yosupo.jp/problem/longest_increasing_subsequence
  INT(N);
  VEC(int, N, A);
  LongestIncreasingSubsequence lis(A);
  dump(lis.idx, lis.cand);
  vector<int> ans(lis.cand.size());
  rep(i, lis.cand.size()) ans[i] = lis.cand[i].front();
  PRINT(ans.size());
  PRINTVEC(ans);
  //*/

  /* https://atcoder.jp/contests/abc354/tasks/abc354_f
  INT(T);
  rep(_, T)
  {
    INT(N);
    VEC(int, N, A);
    LongestIncreasingSubsequence lis(A);
    vector<int> ans;
    rep(i, N) if (lis.idx[i] != -1) ans.push_back(i);
    offset(ans, 1);
    PRINT(ans.size());
    PRINTVEC(ans);
  }
  //*/

  /* https://yukicoder.me/problems/no/1804
  INT(N);
  VEC(int, N, P);
  LongestIncreasingSubsequence lis(P);
  dump(lis.cand);
  vector<int> ans;
  rep(j, lis.cand.size())
  {
    if ((int)lis.cand[j].size() == 1)
    {
      int i = lis.cand[j].front();
      ans.push_back(P[i]);
    }
  }
  PRINT(ans.size());
  PRINTVEC(ans);
  //*/

  //* https://yukicoder.me/problems/no/992
  INT(N);
  VEC(int, N, A);
  LongestIncreasingSubsequence lis(A);
  auto C = lis.cand;
  dump(C);
  vector<mint> dp(C.front().size(), 1), ndp;
  rep(i, 1, C.size())
  {
    ndp.assign(C.at(i).size(), 0);
    // c[i-1][j] < c[i][k] かつ A[c[i-1][j]] > A[c[i][k]] なところに遷移
    {
      int l = 0, r = 0;
      rep(j, dp.size())
      {
        while (l < (int)C.at(i).size() && C.at(i - 1).at(j) > C.at(i).at(l))
          l++;
        while (r < (int)C.at(i).size() && A.at(C.at(i - 1).at(j)) < A.at(C.at(i).at(r)))
          r++;
        dump(i, j, l, r);
        if (l < r)
        {
          ndp.at(l) += dp.at(j);
          if (r < (int)C.at(i).size()) ndp.at(r) -= dp.at(j);
        }
        //dump(ndp);
      }
    }
    rep(k, (int)ndp.size() - 1) ndp.at(k + 1) += ndp.at(k);
    swap(dp, ndp);
    dump(dp);
  }
  mint ans = reduce(ALL(dp));
  PRINT(ans);
  //*/
}

int main()
{
  //*
  #ifndef LOCAL
    cin.tie(0);
    ios::sync_with_stdio(false);
  #endif
  //*/
  cout << fixed << setprecision(20);

  int T = 1;
  /*
  cin >> T;
  //*/
  while (T--)
  {
    main2();
  }
}