#include using namespace std; template struct IntervalSet{ //区間をsetで管理するテク~ T len; set> S; IntervalSet():len(0){} T add(T l,T r){ //[l,r]を追加. auto memolen = len; assert(l <= r); auto itr = S.lower_bound({l,-1}); if(itr != S.begin()) itr--; vector> Era; while(itr != S.end()){ auto [L,R] = *itr; itr++; if(R+1 < l) continue; if(r+1 < L) break; len -= R-L+1,Era.push_back({L,R}); l = min(l,L),r = max(r,R); } for(auto e : Era) S.erase(e); len += r-l+1,S.insert({l,r}); return len-memolen; //追加した区間長. } T era(T l,T r){ //[l,r]を削除. auto memolen = len; assert(l <= r); auto itr = S.lower_bound({l,-1}); if(itr != S.begin()) itr--; vector> Era,Add; while(itr != S.end()){ auto [L,R] = *itr; itr++; if(R < l) continue; if(r < L) break; len -= R-L+1,Era.push_back({L,R}); if(L < l) Add.push_back({L,l-1}); if(r < R) Add.push_back({r+1,R}); } for(auto e : Era) S.erase(e); for(auto a : Add) S.insert(a); for(auto [L,R] : Add) len += R-L+1; return memolen-len; //削除した区間長. } vector> add2(T l,T r){ //[l,r]を追加 追加した区間を返す. assert(l <= r); auto itr = S.lower_bound({l,-1}); if(itr != S.begin()) itr--; vector> Era,ret; long long al = l,ar = r; while(itr != S.end()){ auto [L,R] = *itr; itr++; if(R+1 < l) continue; if(r+1 < L) break; len -= R-L+1,Era.push_back({L,R}); if(al < L) ret.push_back({al,L-1}); l = min(l,L),r = max(r,R),al = R+1; } for(auto e : Era) S.erase(e); len += r-l+1,S.insert({l,r}); if(al <= ar) ret.push_back({al,ar}); return ret; } vector> era2(T l,T r){ //[l,r]を削除 削除した区間を返す. assert(l <= r); auto itr = S.lower_bound({l,-1}); if(itr != S.begin()) itr--; vector> Era,Add,ret; while(itr != S.end()){ auto [L,R] = *itr; itr++; if(R < l) continue; if(r < L) break; len -= R-L+1,Era.push_back({L,R}); T dl = L,dr = R; if(L < l) Add.push_back({L,l-1}),dl = l; if(r < R) Add.push_back({r+1,R}),dr = r; ret.push_back({dl,dr}); } for(auto e : Era) S.erase(e); for(auto a : Add) S.insert(a); for(auto [L,R] : Add) len += R-L+1; return ret; } pair>,vector>> add3(T l,T r){ //[l,r]を追加 変わった区間を返す. assert(l <= r); auto itr = S.lower_bound({l,-1}); if(itr != S.begin()) itr--; vector> Era; while(itr != S.end()){ auto [L,R] = *itr; itr++; if(R+1 < l) continue; if(r+1 < L) break; len -= R-L+1; Era.push_back({L,R}); l = min(l,L),r = max(r,R); } for(auto e : Era) S.erase(e); len += r-l+1,S.insert({l,r}); return {{{l,r}},Era}; } pair>,vector>> era3(T l,T r){ //[l,r]を削除 変わった区間を返す. assert(l <= r); auto itr = S.lower_bound({l,-1}); if(itr != S.begin()) itr--; vector> Era,Add; while(itr != S.end()){ auto [L,R] = *itr; itr++; if(R < l) continue; if(r < L) break; len -= R-L+1,Era.push_back({L,R}); if(L < l) Add.push_back({L,l-1}); if(r < R) Add.push_back({r+1,R}); } for(auto e : Era) S.erase(e); for(auto a : Add) S.insert(a); for(auto [L,R] : Add) len += R-L+1; return {Add,Era}; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector A(N); for(auto &a : A) cin >> a; IntervalSet S; long long answer = 0; for(auto a : A){ auto itr = S.S.lower_bound({a+1,-1}); if(itr == S.S.begin()) S.add(a,a); else{ itr--; auto [l,r] = *itr; if(l <= a && a <= r){ S.era(l,r); long long left = a-l+1,right = r-a+1,len = r-l+1,len2 = len+2-2*min(left,right); answer += (len+len2)*min(left,right)/2; S.add(l-1,l-1+right-1),S.add(r+1-left+1,r+1); } else S.add(a,a); } } cout << answer << endl; }