\(P\) の隣接要素の大小関係を表す長さ \(N - 1\) の文字列 \(S\) をとります。すなわち、<, > からなる長さ \(N - 1\) の文字列 \(S\) であって、\(P_i < P_{i + 1}\) のとき \(S_i =\) <、\(P_i > P_{i + 1}\) のとき \(S_i =\) > であるものをとります。

このとき、数列 \((P_l, P_{l + 1}, \ldots, P_r)\) がチルダ型であることは \(S\) の部分文字列 \(S_lS_{l + 1} \ldots S_{r - 1}\) が \(1\) 個以上の <, \(1\) 個以上の >, \(1\) 個以上の < をこの順に結合した文字列となることと同値です。

以上により、本問題は \(S\) の連続部分列であって \(1\) 個以上の <, \(1\) 個以上の >, \(1\) 個以上の < をこの順に結合した文字列であるものの個数を数えることに帰着されます。

ここで、\(S\) のランレングス圧縮を考えます。例えば、\(S =\) ><<>><<<<> のとき、ランレングス圧縮により得られる列は \((\) >1, <2, >2, <4, >1 \()\) のようになります。

「\(1\) 個以上の >」の部分に着目すると、これはランレングス圧縮後の（文字が > である）一つの要素に対応します。これにより数え上げるべき文字列の「\(1\) 個以上の >」の部分を全探索する方針が立ちます。「\(1\) 個以上の >」の部分を固定したとき、ランレングス圧縮した列における左の要素の < の個数を \(a\)、右の要素の < の個数を \(b\) とすると、左に続く < の個数は \(1, 2, \ldots, a\)、右に続く < の個数は \(1, 2, \ldots, b\) が考えられるため、数え上げるべき文字列の個数は \(ab\) です。この値を足し合わせることにより、答えを得ることができます。

実装例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	int n;
	cin >> n;
	vector<int> p(n);
	for (int i = 0; i < n; i++) cin >> p[i];
	vector<pair<char, ll>> v;
	for (int i = 0; i < n - 1; i++) {
		if (p[i] < p[i + 1]) {
			if (v.empty() or v.back().first == '>') v.push_back({ '<', 1 });
			else v.back().second++;
		}
		else {
			if (v.empty() or v.back().first == '<') v.push_back({ '>', 1 });
			else v.back().second++;
		}
	}
	int sz = ssize(v);
	ll ans = 0;
	for (int i = 1; i < sz - 1; i++) if (v[i].first == '>') ans += v[i - 1].second * v[i + 1].second;
	cout << ans << '\n';
}