#ifdef ONLINE_JUDGE #pragma GCC target("avx2,avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #include using namespace std; using ll = long long; using ull = unsigned long long; using i128 = __int128_t; using pii = pair; using pll = pair; #define rep(i, n) for (int i = 0; i < (n); i++) #define all(x) (x).begin(), (x).end() constexpr char ln = '\n'; istream& operator>>(istream& is, __int128_t& x) { x = 0; string s; is >> s; int n = int(s.size()), it = 0; if (s[0] == '-') it++; for (; it < n; it++) x = (x * 10 + s[it] - '0'); if (s[0] == '-') x = -x; return is; } ostream& operator<<(ostream& os, __int128_t x) { if (x == 0) return os << 0; if (x < 0) os << '-', x = -x; deque deq; while (x) deq.emplace_front(x % 10), x /= 10; for (int e : deq) os << e; return os; } template ostream& operator<<(ostream& os, const pair& p) { return os << "(" << p.first << ", " << p.second << ")"; } template ostream& operator<<(ostream& os, const vector& v) { os << "{"; for (int i = 0; i < int(v.size()); i++) { if (i) os << ", "; os << v[i]; } return os << "}"; } template inline int SZ(Container& v) { return int(v.size()); } template inline void UNIQUE(vector& v) { v.erase(unique(v.begin(), v.end()), v.end()); } template inline bool chmax(T1& a, T2 b) { if (a < b) {a = b; return true ;} return false ;} template inline bool chmin(T1& a, T2 b) { if (a > b) {a = b; return true ;} return false ;} inline int topbit(int x) { return x == 0 ? -1 : 31 - __builtin_clz(x); } inline int topbit(long long x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); } inline int botbit(int x) { return x == 0 ? 32 : __builtin_ctz(x); } inline int botbit(long long x) { return x == 0 ? 64 : __builtin_ctzll(x); } inline int popcount(int x) { return __builtin_popcount(x); } inline int popcount(long long x) { return __builtin_popcountll(x); } inline int kthbit(long long x, int k) { return (x>>k) & 1; } inline constexpr long long TEN(int x) { return x == 0 ? 1 : TEN(x-1) * 10; } namespace detail { template auto make_vector(vector& sizes, Tp const& x) { if constexpr (Nb == 1) { return vector(sizes[0], x); } else { int size = sizes[Nb-1]; sizes.pop_back(); return vector(size, make_vector(sizes, x)); } } } template auto make_vector(int const(&sizes)[Nb], Tp const& x = Tp()) { vector s(Nb); for (int i = 0; i < Nb; i++) s[i] = sizes[Nb-i-1]; return detail::make_vector(s, x); } inline void print() { cout << "\n"; } template inline void print(const vector& v) { for (int i = 0; i < int(v.size()); i++) { if (i) cout << " "; cout << v[i]; } print(); } template inline void print(const T& x, const Args& ... args) { cout << x << " "; print(args...); } #ifdef MINATO_LOCAL inline void debug_out() { cerr << endl; } template inline void debug_out(const T& x, const Args& ... args) { cerr << " " << x; debug_out(args...); } #define debug(...) cerr << __LINE__ << " : [" << #__VA_ARGS__ << "] =", debug_out(__VA_ARGS__) #define dump(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl #else #define debug(...) (void(0)) #define dump(x) (void(0)) #endif struct fast_ios { fast_ios() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// template struct SegmentTree { private: F op; T e; int _n, size ,log; vector node; public: SegmentTree() {} SegmentTree(const F& op, T e, int n) : SegmentTree(op, e, vector(n, e)) {} SegmentTree(const F& op, T e, const vector& v) : op(op), e(e), _n(int(v.size())), log(0) { while ((1< (2 * size, e); for (int i = 0; i < _n; i++) node[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } // (0-indexed) void set(int p, T x) { assert(0 <= p && p < _n); p += size; node[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } // [l, r) (0-indexed) T get(int l, int r) { if (l >= r) return e; T resl = e, resr = e; l += size; r += size; while (l < r) { if (l & 1) resl = op(resl, node[l++]); l >>= 1; if (r & 1) resr = op(node[--r], resr); r >>= 1; } return op(resl, resr); } T all_get() { return node[1]; } template int max_right(int l, const C& check) { assert(0 <= l && l <= _n); assert(check(e)); if (l == _n) return _n; l += size; T sm = e; do { while (~l & 1) l >>= 1; if (!check(op(sm, node[l]))) { while (l < size) { l = (2 * l); if (check(op(sm, node[l]))) { sm = op(sm, node[l]); l++; } } return l - size; } sm = op(sm, node[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r, const C& check) { assert(0 <= r && r <= _n); assert(check(e)); if (r == 0) return 0; r += size; T sm = e; do { r--; while (r > 1 && (r & 1)) r >>= 1; if (!check(op(node[r], sm))) { while (r < size) { r = (2 * r + 1); if (check(op(node[r], sm))) { sm = op(node[r], sm); r--; } } return r + 1 - size; } sm = op(node[r], sm); } while ((r & -r) != r); return 0; } T operator[](int p) { assert(0 <= p && p < _n); return node[p + size]; } private: void update(int k) { node[k] = op(node[2 * k], node[2 * k + 1]); } }; struct SuccinctIndexableDictionary { size_t length; size_t blocks; vector bit, sum; SuccinctIndexableDictionary() = default; SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) { bit.assign(blocks, 0U); sum.assign(blocks, 0U); } void set(int k) { bit[k >> 5] |= 1U << (k & 31); } void build() { sum[0] = 0U; for(int i = 1; i < int(blocks); i++) { sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]); } } bool operator[](int k) { return (bool((bit[k >> 5] >> (k & 31)) & 1)); } int rank(int k) { return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1))); } int rank(bool val, int k) { return (val ? rank(k) : k - rank(k)); } }; template struct WaveletMatrix { size_t length; SuccinctIndexableDictionary matrix[MAXLOG]; int mid[MAXLOG]; WaveletMatrix() = default; WaveletMatrix(vector v) : length(v.size()) { vector< T > l(length), r(length); for(int level = MAXLOG - 1; level >= 0; level--) { matrix[level] = SuccinctIndexableDictionary(length + 1); int left = 0, right = 0; for(int i = 0; i < int(length); i++) { if(((v[i] >> level) & 1)) { matrix[level].set(i); r[right++] = v[i]; } else { l[left++] = v[i]; } } mid[level] = left; matrix[level].build(); v.swap(l); for(int i = 0; i < right; i++) { v[left + i] = r[i]; } } } pair< int, int > succ(bool f, int l, int r, int level) { return {matrix[level].rank(f, l) + mid[level] * f, matrix[level].rank(f, r) + mid[level] * f}; } // v[k] T access(int k) { T ret = 0; for(int level = MAXLOG - 1; level >= 0; level--) { bool f = matrix[level][k]; if(f) ret |= T(1) << level; k = matrix[level].rank(f, k) + mid[level] * f; } return ret; } T operator[](const int &k) { return access(k); } // count i s.t. (0 <= i < r) && v[i] == x int rank(const T &x, int r) { int l = 0; for(int level = MAXLOG - 1; level >= 0; level--) { tie(l, r) = succ((x >> level) & 1, l, r, level); } return r - l; } // k-th(0-indexed) smallest number in v[l,r) T kth_smallest(int l, int r, int k) { assert(0 <= k && k < r - l); T ret = 0; for(int level = MAXLOG - 1; level >= 0; level--) { int cnt = matrix[level].rank(false, r) - matrix[level].rank(false, l); bool f = cnt <= k; if(f) { ret |= T(1) << level; k -= cnt; } tie(l, r) = succ(f, l, r, level); } return ret; } // k-th(0-indexed) largest number in v[l,r) T kth_largest(int l, int r, int k) { return kth_smallest(l, r, r - l - k - 1); } // count i s.t. (l <= i < r) && (v[i] < upper) int range_freq(int l, int r, T upper) { int ret = 0; for(int level = MAXLOG - 1; level >= 0; level--) { bool f = ((upper >> level) & 1); if(f) ret += matrix[level].rank(false, r) - matrix[level].rank(false, l); tie(l, r) = succ(f, l, r, level); } return ret; } // count i s.t. (l <= i < r) && (lower <= v[i] < upper) int range_freq(int l, int r, T lower, T upper) { return range_freq(l, r, upper) - range_freq(l, r, lower); } // max v[i] s.t. (l <= i < r) && (v[i] < upper) T prev_value(int l, int r, T upper) { int cnt = range_freq(l, r, upper); return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1); } // min v[i] s.t. (l <= i < r) && (lower <= v[i]) T next_value(int l, int r, T lower) { int cnt = range_freq(l, r, lower); return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt); } }; int main() { int N; cin >> N; vector p(N); rep(i,N) cin >> p[i]; auto f=[](int a, int b) {return max(a,b);}; auto g=[](int a, int b) {return min(a,b);}; constexpr int emax = -1; constexpr int emin = 1e9; SegmentTree seg1(f,emax,p); SegmentTree seg2(g,emin,p); vector MAX(N),MIN(N); rep(i,N) { auto check1=[&](int a) {return a <= p[i];}; auto check2=[&](int a) {return a >= p[i];}; int l = seg1.min_left(i+1,check1); int r = seg1.max_right(i,check1); MAX[i] = pii(l,r); l = seg2.min_left(i+1,check2); r = seg2.max_right(i,check2); MIN[i] = pii(l,r); } vector MIN_L(N),MIN_R(N); rep(i,N) { MIN_L[i] = MIN[i].first; MIN_R[i] = MIN[i].second; } WaveletMatrix WML(MIN_L),WMR(MIN_R); ll ans = 0; auto rec=[&](auto self, int l, int r)->void { if (r-l==1) return; int m = (l+r)/2; self(self,l,m); self(self,m,r); for (int pos = l; pos < r; pos++) { if (pos < m) { int rb = min(MAX[pos].second,r); if (rb <= m) continue; ans += WML.range_freq(m,rb,pos+1); } else { int lb = max(MAX[pos].first,l); if (lb >= m) continue; ans += WMR.range_freq(lb,m,pos+1,2e5); } } return; }; rec(rec,0,N); cout << ans << ln; }