#include #include #include template std::vector vec(int len, T elem) { return std::vector(len, elem); } using lint = long long; void solve() { int n; std::cin >> n; std::vector xs(n); for (auto& x : xs) std::cin >> x; lint ans = 0; for (int q = 0; q < 2; ++q) { std::vector to(n + 1, n), lim(n + 1, n); std::vector> ps; for (int i = 0; i < n; ++i) { while (!ps.empty() && ps.back().first < xs[i]) { to[ps.back().second] = i; ps.pop_back(); } ps.emplace_back(xs[i], i); } ps.clear(); for (int i = 0; i < n; ++i) { while (!ps.empty() && ps.back().first > xs[i]) { lim[ps.back().second] = i; ps.pop_back(); } ps.emplace_back(xs[i], i); } auto tab = vec(20, vec(n + 1, n)); tab[0] = to; for (int k = 1; k < 20; ++k) { for (int i = 0; i <= n; ++i) { tab[k][i] = tab[k - 1][tab[k - 1][i]]; } } for (int i = 0; i < n; ++i) { int v = i; for (int k = 19; k >= 0; --k) { if (tab[k][v] < lim[i]) { ans += (1 << k); v = tab[k][v]; } } } std::reverse(xs.begin(), xs.end()); } std::cout << ans << std::endl; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }