//#define _GLIBCXX_DEBUG #include using namespace std; #define rep(i, n) for(int i=0; i; using vs = vector; using vi = vector; using vvi = vector; template using PQ = priority_queue; template using PQG = priority_queue, greater>; const int INF = 0xccccccc; const ll LINF = 0xcccccccccccccccLL; template inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);} template inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);} template istream &operator>>(istream &is, pair &p) { return is >> p.first >> p.second;} template ostream &operator<<(ostream &os, const pair &p) { return os << p.first << ' ' << p.second;} template struct SWAG { using FX = function; stack> frst, bcst; FX fx; const T ex; //fx(新, 古) SWAG(FX fx_, T ex_):fx(fx_), ex(ex_) {} void push(T x) { bcst.emplace(x, fx(x, (bcst.empty()?ex:bcst.top().second))); } void pop() { if(frst.empty()) { while(!bcst.empty()) { frst.emplace(bcst.top().first, fx((frst.empty()?ex:frst.top().second), bcst.top().first)); bcst.pop(); } } assert(!frst.empty()); frst.pop(); } T calc() { return fx(bcst.empty()?ex:bcst.top().second, frst.empty()?ex:frst.top().second); } }; struct S { int m1, m2, M; int calc() {return m1+m2-M;} }; //head int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vi a(n); rep(i, n) cin >> a[i]; auto fx = [](S a, S b)->S { if(a.m1 > b.m1) swap(a, b); return {a.m1, min(a.m2, b.m1), max(a.M, b.M)}; }; SWAG s(fx, S({INT_MAX/2, INT_MAX/2, 0})); ll ans = 0; int j = 0; rep(i, n-1) { while(j < n and s.calc().calc() >= 0) { s.push({a[j], INT_MAX/2, a[j]}); j++; } ans += j-i-1; s.pop(); } cout << ans << endl; }