Define a string \(S\) of length \((N-1)\) that represents orderings of adjacent elements of \(P\) as follows: \(S_i =\) < if \(P_i < P_{i + 1}\) and \(S_i =\) > if \(P_i > P_{i + 1}\).

Then, a sequence \((P_l, P_{l + 1}, \ldots, P_r)\) is tilde-shaped if and only if \(S_lS_{l + 1} \ldots S_{r - 1}\) is a concatenation of one or more <, one or more >, and one or more <, in this order.

Therefore, the problem is reduced to counting the number of substrings of \(S\) formed by concatenating one or more <, one or more >, and one or more <, in this order.

Now, consider the run-length compression of \(S\). For example, applying the run-length compression against \(S =\) ><<>><<<<> yields a sequence \((\) >1, <2, >2, <4, >1 \()\).

The “one or more >” part corresponds to an element of the result of the run-length compression (representing repeated >). This motivates us to brute-force over the “one or more >” part. When this part is fixed, let \(a\) be the number of < to its left, and \(b\) be the number of < to its right. Then the number of left < in the resulting string can be one of \(1, 2, \ldots, a\), and that for right can be \(1, 2, \ldots, b\), so there are \(ab\) applicable strings. The sum of this value is the answer.

Sample code

#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';
}