DP 状态取值不多这件事情一般很难发现，所以很容易被被刺，做题时需要考虑这种可能性。

首先考虑如何判定。

这种将一个序列划分为两个序列的东西，有通用的设计 DP 状态的办法： 表示 在序列 中时，另一个序列需要记录的信息。

回到这里就是： 表示 在递增序列时，递减序列末位数的最大值； 表示 在递减序列时，递增序列某位数的最小值。这里记录的值是对后面限制最松的情况，最优性显然。转移时讨论 和 在哪个序列即可。无解就是 。

考虑如何算合法区间个数。首先，对于固定的 ，合法的 一定是某个区间。只需求出最大的合法的 即可。

这个 DP 形式看上去就很难用 DS 动态维护。故考虑在 变化时暴力更新所有 的 DP 值。因为 的 DP 值只与 有关，所以如果某次更新没有产生影响，那后面的数就都不需要更新了。

因为 DP 值的变化是单调的，所以暴力更新的开销跟所有 DP 值的取值个数之和是同阶的。事实上，每个 DP 值的取值个数不是很多。以 为例，我们找到最大的 满足 。那么 和 中必须有一个在递减序列中。因为 后面的数都是递增的，所以递减序列的最小值只可能在 或 中取（当然还有 ）。所以单个 只有最多 种取值。 同理。综上所述，每个 值最多被更新 次，故更新的总开销是 的。（如果不存在 ，情况是平凡的）

综上所述，我们在 的复杂度解决了此题。

#include <bits/stdc++.h>
template<typename T> inline bool ckmax(T &x,const T &y) { return (x < y) && (x = y,true);}
template<typename T> inline bool ckmin(T &x,const T &y) { return (x > y) && (x = y,true);}
const int N = 2e5 + 5;
int n;
int p[N];
int inc[N],dec[N];
int main() {
	std::cin >> n;
	for(int i = 1;i <= n;i++) std::cin >> p[i];
	for(int i = 1;i <= n;i++) inc[i] = 0,dec[i] = n + 1;
	long long ans = 0;
	for(int i = n,r = n;i;i--) {
		inc[i] = n + 1;dec[i] = 0;
		for(int j = i + 1;j <= n;j++) {
			int ni = 0,nd = n + 1;
			if(p[j - 1] < p[j]) ckmax(ni,inc[j - 1]);
			if(p[j - 1] > p[j]) ckmin(nd,dec[j - 1]);
			if(inc[j - 1] > p[j]) ckmin(nd,p[j - 1]);
			if(dec[j - 1] < p[j]) ckmax(ni,p[j - 1]);
			if(ni == inc[j] && nd == dec[j]) break;
			inc[j] = ni;dec[j] = nd;
		}
		while(r >= i && (inc[r] == 0 && dec[r] == n + 1))
			--r;
		ans += (r - i + 1);
	}
	std::cout << ans << std::endl;
	return 0;
}