怎么其他两篇题解都是 \(O(n\log n)\) 的，来发一个 \(O(n)\) 做法，当考前复习了。
对原序列建出小根笛卡尔树，节点编号与原序列中的下标相同。记 \(T_u\) 表示以 \(u\) 为根的子树，\(lc(u),rc(u)\) 分别表示 \(u\) 的左儿子和右儿子。
设 \(f_u\) 表示删除若干 \(T_u\) 中的点（可以不删），但不能删空的方案数。
假设节点 \(u\) 没有删除，此时左右子树可以删空也可以不删空，有转移：
\[f_u\gets(f_{lc(u)}+1)(f_{rc(u)}+1)
\]
节点 \(u\) 可以被删除，当且仅当其左侧存在比它小的数且它们中间所有数都被删了，或者其右侧存在比它小的数且它们中间所有数都被删了。根据笛卡尔树性质，假设 \(T_u\) 的下标范围是 \([l_u,r_u]\)，则 \(l_u-1,r_u+1\) 两个下标的数如果存在，必定比 \(u\) 下标的数要小。根据这一点，有转移：
\[\begin{cases}
f_u\gets f_{rc(u)}&\textrm{if }l_u > 1\\
f_u\gets f_{lc(u)}&\textrm{if }r_u > 1\\
\end{cases}
\]
时间复杂度 \(O(n)\)。
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
template<int mod>
inline unsigned int down(unsigned int x) {
return x < mod ? x : x - mod;
}
template<int mod>
struct Modint {
unsigned int x;
Modint() = default;
Modint(int x) : x(x) {}
friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
friend Modint operator^(Modint a, int k) {Modint ans = 1; for(; k; k >>= 1, a *= a) if(k & 1) ans *= a; return ans;}
friend Modint operator~(Modint a) {return a ^ (mod - 2);}
friend Modint operator/(Modint a, Modint b) {return a * ~b;}
friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
friend Modint& operator^=(Modint& a, int k) {return a = a ^ k;}
friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
friend Modint& operator++(Modint& a) {return a += 1;}
friend Modint operator++(Modint& a, int) {Modint b = a; ++a; return b;}
friend Modint& operator--(Modint& a) {return a -= 1;}
friend Modint operator--(Modint& a, int) {Modint b = a; --a; return b;}
friend Modint operator-(Modint a) {return a.x == 0 ? 0 : mod - a.x;}
friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};
typedef Modint<1000000007> mint;
const int N = 3e5 + 5;
int n, a[N], lc[N], rc[N], stk[N], top;
mint dp[N];
void dfs(int u, int l, int r) {
if(lc[u]) dfs(lc[u], l, u - 1);
if(rc[u]) dfs(rc[u], u + 1, r);
dp[u] += (dp[lc[u]] + 1) * (dp[rc[u]] + 1);
if(l > 1) dp[u] += dp[rc[u]];
if(r < n) dp[u] += dp[lc[u]];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
rep(i, 1, n) cin >> a[i];
stk[++top] = 1;
rep(i, 2, n) {
while(top && a[stk[top]] > a[i]) --top;
if(!top) lc[i] = stk[1];
else {
lc[i] = rc[stk[top]];
rc[stk[top]] = i;
}
stk[++top] = i;
}
int rt = min_element(a + 1, a + 1 + n) - a;
dfs(rt, 1, n);
cout << dp[rt] << endl;
return 0;
}