#include using namespace std; #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; } template bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; } // 0-indexed BIT (binary indexed tree / Fenwick tree) (i : [0, len)) template struct BIT { int n; std::vector data; BIT(int len = 0) : n(len), data(len) {} void reset() { std::fill(data.begin(), data.end(), T(0)); } void add(int pos, T v) { // a[pos] += v pos++; while (pos > 0 and pos <= n) data[pos - 1] += v, pos += pos & -pos; } T sum(int k) const { // a[0] + ... + a[k - 1] T res = 0; while (k > 0) res += data[k - 1], k -= k & -k; return res; } T sum(int l, int r) const { return sum(r) - sum(l); } // a[l] + ... + a[r - 1] }; // Simple forward_list for MLE-sensitive situations // Verify: template struct light_forward_list { static std::vector ptr; static std::vector val; unsigned head; light_forward_list() : head(0) {} void push_front(T x) { ptr.push_back(head), val.push_back(x); head = ptr.size() - 1; } struct iterator { unsigned p; iterator operator++() { return {p = ptr[p]}; } T &operator*() { return val[p]; } bool operator!=(const iterator &rhs) { return p != rhs.p; } }; iterator begin() { return {head}; } iterator end() { return {0}; } }; template std::vector light_forward_list::ptr = {0}; template std::vector light_forward_list::val = {T()}; int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N; cin >> N; vector A(N); for (auto &a : A) cin >> a, a--; vector pos(N); REP(i, N) pos[A[i]] = i; BIT bit(N + 1); using pint = pair; vector lohi(N); vector> bged(N + 1); REP(i, N) { bool md = false; int lo = 0, hi = N; if (i == 0) { md = (A[i + 1] < A[i]); } else { md = (A[i - 1] < A[i]); } if (md) { hi = N; if (i) chmax(lo, A[i - 1] + 1); if (i + 1 < N) chmax(lo, A[i + 1] + 1); } else { lo = 0; if (i) chmin(hi, A[i - 1]); if (i + 1 < N) chmin(hi, A[i + 1]); } lohi[i] = make_pair(lo, hi); bged[lo].push_front(pint(A[i], 1)); if (hi < N) bged[hi].push_front(pint(A[i], -1)); } uint64_t ret = 0; REP(a, N) { for (auto [b, v] : bged[a]) { bit.add(b, v); } auto [l, r] = lohi[pos[a]]; ret += bit.sum(l, r); } cout << (ret - N) / 2 << '\n'; }