結果

問題 No.3801 Split Pairs
コンテスト
ユーザー yuki4869.
提出日時 2026-11-14 00:01:35
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 157 ms / 2,000 ms
+ 515µs
コード長 23,726 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,883 ms
コンパイル使用メモリ 399,108 KB
実行使用メモリ 17,536 KB
最終ジャッジ日時 2026-11-14 00:01:45
合計ジャッジ時間 10,558 ms
ジャッジサーバーID
(参考情報)
judge4_0 / judge3_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

// https://github.com/yuki-4869/Algorithm/blob/main/template.cpp
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std; using namespace atcoder;
using ll=long long; using LL=__int128; using mint=modint998244353;
using ld = long double;
using pll=pair<ll,ll>; using tu=tuple<ll,ll,ll>; using tu4 = tuple<ll,ll,ll,ll>;using vl=vector<ll>; using vb=vector<bool>; using vvb=vector<vb>; using vvl=vector<vl>; using vs=vector<string>; using vld=vector<long double>; using vc=vector<char>; using vmi=vector<mint>; using vp = vector<pll>; using vt = vector<tu>;using graph = vvl; using Graph = vector<vp>;
template<class T=ll> auto vec2(ll n,ll m,T x=T()){return vector(n,vector<T>(m,x));} template<class T=ll> auto vec3(ll n,ll m,ll l,T x=T()){return vector(n,vector(m,vector<T>(l,x)));}
template<class T=ll> auto vec4(ll a,ll b,ll c,ll d,T x=T()){return vector(a,vector(b,vector(c,vector<T>(d,x))));}
template<class T> using rpq=priority_queue<T,vector<T>,greater<T>>; // 小さい順priority_queue
using inverse_priority_queue=rpq<ll>;
const ll Inf=2147483647LL, Inf9=1000000000LL, inf=9223372036854775807LL, inf18=1000000000000000000LL, mod=998244353LL;
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define Re(n) for(ll i = 0; i<(ll)(n);i++)
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)
#define rep3(i,s,t) for(ll i=(ll)(s);i<(ll)(t);i++)
#define pb push_back
#define p(s) cout<<(s)<<'\n'
#define p2(s,t) cout<<(s)<<" "<<(t)<<'\n'
#define p3(s,t,u) cout<<(s)<<" "<<(t)<<" "<<(u)<<'\n'
#define p4(s,t,u,v) cout<<(s)<<" "<<(t)<<" "<<(u)<<" "<<(v)<<'\n'
#define pe(s) cout<<(s)<<endl
#define pld(...) ([](const auto&... values)->std::ostream&{auto flags=std::cout.flags();auto precision=std::cout.precision();std::cout<<std::fixed<<std::setprecision(12);size_t i=0;((std::cout<<(i++?" ":"")<<static_cast<long double>(values)),...);std::cout<<'\n';std::cout.flags(flags);std::cout.precision(precision);return std::cout;}(__VA_ARGS__))
#define pld2(s,t) pld((s),(t))
#define pld3(s,t,u) pld((s),(t),(u))
#define pld4(s,t,u,v) pld((s),(t),(u),(v))
#define pe2(s,t) cout<<(s)<<" "<<(t)<<endl
#define pe3(s,t,u) cout<<(s)<<" "<<(t)<<" "<<(u)<<endl
#define pe4(s,t,u,v) cout<<(s)<<" "<<(t)<<" "<<(u)<<" "<<(v)<<endl
#define pval(s) cout<<(s).val()<<'\n'
#define Sort(A) sort(all(A))
#define RSort(A) sort(rall(A))
#define p_yes() p("Yes")
#define p_no() p("No")

template<class T> inline ll sz(const T& x){return (ll)x.size();} // サイズ取得
ostream& operator<<(ostream& os,const mint& x){return os<<x.val();} // mint出力
istream& operator>>(istream& is,mint& x){ll v; is>>v; x=mint(v); return is;} // mint入力
template<class T> inline bool chmin(T& a,const T& b){if(a>b){a=b; return true;} return false;} // 最小値更新
template<class T> inline bool chmax(T& a,const T& b){if(a<b){a=b; return true;} return false;} // 最大値更新
template<class T,class U> ll LB(const vector<T>& v,const U& a){return lower_bound(all(v),a)-v.begin();} // lower_boundのindex
template<class T,class U> ll UB(const vector<T>& v,const U& a){return upper_bound(all(v),a)-v.begin();} // upper_boundのindex
template<class T> T vec_min(const vector<T>& v){do { if (!(!v.empty())) std::abort(); } while (false); return *min_element(all(v));} // vectorの最小値
template<class T> T vec_max(const vector<T>& v){do { if (!(!v.empty())) std::abort(); } while (false); return *max_element(all(v));} // vectorの最大値
template<class T> T vec_sum(const vector<T>& v){T res=T(0); for(const auto& x:v) res+=x; return res;} // vectorの総和

template<class T=ll> vector<T> cin_vl(ll n){vector<T> ret(n); rep(i,n) cin>>ret[i]; return ret;} // vector入力、型省略時ll
template<class T=ll> vector<vector<T>> cin_vvl(ll h,ll w){vector<vector<T>> ret(h,vector<T>(w)); rep(i,h) rep(j,w) cin>>ret[i][j]; return ret;} // h*w入力、型省略時ll
template<class T=ll> pair<vector<T>,vector<T>> cin_xy(ll n){vector<T> x(n),y(n); rep(i,n) cin>>x[i]>>y[i]; return {x,y};} // x,y入力、型省略時ll
template<class T=ll> tuple<vector<T>,vector<T>,vector<T>> cin_xyz(ll n){vector<T> x(n),y(n),z(n); rep(i,n) cin>>x[i]>>y[i]>>z[i]; return {x,y,z};} // x,y,z入力、型省略時ll
template<class T=ll> vector<vector<T>> Cin_vl(ll n,ll k){vector<vector<T>> ret(k,vector<T>(n)); rep(i,n) rep(j,k) cin>>ret[j][i]; return ret;} // n行k列入力を列ごと保持、型省略時ll
template<class T=ll> vector<pair<T,T>> cin_pairs(ll n){vector<pair<T,T>> ret(n); rep(i,n) cin>>ret[i].first>>ret[i].second; return ret;} // pair列入力、型省略時ll
template<class T=ll> vector<tuple<T,T,T>> cin_tuples(ll n){vector<tuple<T,T,T>> ret(n); rep(i,n){T a,b,c; cin>>a>>b>>c; ret[i]={a,b,c};} return ret;} // 3要素tuple列入力、型省略時ll

template<class T> void cout_vl(const vector<T>& a,char sep=' ',char end='\n'){rep(i,sz(a)){if(i) cout<<sep; cout<<a[i];} cout<<end;} // vector出力
template<class T> void cout_ver(const vector<T>& a){for(const auto& value:a) cout<<value<<'\n';}
template<class T> void Cout_vl(const vector<T>& a,const vector<T>& b){rep(i,sz(a)) cout<<a[i]<<" "<<b[i]<<'\n';} // 2vector縦出力
template<class T> void cout_vvl(const vector<vector<T>>& a){for(const auto& e:a) cout_vl(e);} // 2次元vector出力
template<class T=ll> void Swap(vector<vector<T>>& v,ll& h,ll& w){vector<vector<T>> ret(w,vector<T>(h));rep(i,h) rep(j,w) ret[j][i]=v[i][j];v.swap(ret);swap(h,w);} // h*w行列をw*h行列に変換 hとwを自動でswap

ll ceil_div(ll a,ll b){do { if (!(b!=0)) std::abort(); } while (false); if(b<0) a=-a,b=-b; if(a>=0) return (a+b-1)/b; return -((-a)/b);} // 切り上げ除算
ll floor_div(ll a,ll b){do { if (!(b!=0)) std::abort(); } while (false); if(b<0) a=-a,b=-b; if(a>=0) return a/b; return -((-a+b-1)/b);} // 切り下げ除算
ll isqrt(ll n){ll x=sqrtl(n); while((LL)(x+1)*(x+1)<=n) x++; while((LL)x*x>n) x--; return x;} // floor(sqrt(n))
template<class T> vector<T> sort_unique_vec(vector<T> v){sort(all(v)); v.erase(unique(all(v)),v.end()); return v;} // sortして重複削除した新vector
template<class T> vector<ll> compress(const vector<T>& v){auto xs=sort_unique_vec(v); vector<ll> ret; for(auto& x:v) ret.pb(LB(xs,x)); return ret;} // 座標圧縮後のindex列
template<class T> vector<T> prefix_sum(const vector<T>& v){vector<T> s(sz(v)+1,0); rep(i,sz(v)) s[i+1]=s[i]+v[i]; return s;} // 1次元累積和
template<class T> vector<vector<T>> prefix_sum2(const vector<vector<T>>& a){int h=sz(a),w=sz(a[0]); vector<vector<T>> s(h+1,vector<T>(w+1,0)); rep(i,h)rep(j,w)s[i+1][j+1]=s[i+1][j]+s[i][j+1]-s[i][j]+a[i][j]; return s;} // 2次元累積和
template<class T> T range_sum(const vector<T>& s,ll l,ll r){return s[r]-s[l];} // 累積和から[l,r)の和
template<class T> vector<pair<T,ll>> run_length(const vector<T>& v){vector<pair<T,ll>> ret; for(auto& x:v){if(ret.empty()||ret.back().first!=x) ret.pb({x,1}); else ret.back().second++;} return ret;} // ランレングス圧縮
vector<pair<char,ll>> run_length(const string& s){vector<pair<char,ll>> ret; for(char c:s){if(ret.empty()||ret.back().first!=c) ret.pb({c,1}); else ret.back().second++;} return ret;} // 文字列ランレングス圧縮
template<class T> ll argmin(const vector<T>& v){do { if (!(!v.empty())) std::abort(); } while (false); return min_element(all(v))-v.begin();} // 最小値のindex
template<class T> ll argmax(const vector<T>& v){do { if (!(!v.empty())) std::abort(); } while (false); return max_element(all(v))-v.begin();} // 最大値のindex
template<class T> bool in_vec(const vector<T>& v,const T& x){return binary_search(all(v),x);} // sort済vectorに存在するか

bool even(ll x){return x%2==0;}
bool odd(ll x){return x%2!=0;}
ll grid_id(ll x,ll y,ll w){return x*w+y;} // 座標からGridのID
pll grid_xy(ll id,ll w){return {id/w,id%w};} // GridのIDから座標

ll gcd(ll a,ll b){if(b==0) return abs(a); return gcd(b,a%b);} // 最大公約数
ll lcm(ll a,ll b){return a/gcd(a,b)*b;} // 最小公倍数
ll Exp(ll x,ll y){ll cnt=-1; while(x>0) x/=y,cnt++; return cnt;} // y進桁数-1
ll powmod(ll x,ll k,ll m){if(k==0) return 1%m; ll r=powmod(x,k/2,m); r=(LL)r*r%m; if(k&1) r=(LL)r*x%m; return r;} // mod累乗
template<class T> T square(T x){return x*x;} // 二乗
template<class T> void Uni_erase(vector<T>& v){sort(all(v)); v.erase(unique(all(v)),v.end());} // sortして重複削除
inline bool OutIn(ll x,ll n){return 0<=x&&x<n;}
inline bool OutIn(ll x,ll y,ll h,ll w){return 0<=x&&x<h&&0<=y&&y<w;}
inline bool OutIn(ll x,ll y,ll z,ll a,ll b,ll c){return 0<=x&&x<a&&0<=y&&y<b&&0<=z&&z<c;} // グリッド範囲内判定
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll Random(ll l,ll r){uniform_int_distribution<ll> dist(l,r-1); return dist(rng);} // [l,r)乱数
void YesNo(bool x){x?p_yes():p_no();} // Yes/No出力
vl vl_n(ll n){vl ret(n); rep(i,n) ret[i]=i; return ret;} // 0..n-1のvector生成
vl vl_N(ll n){vl ret(n); rep(i,n) ret[i]=i+1; return ret;} // 1..nのvector生成
vl dijkstra(const graph& g,const vl& starts){ vl dist(g.size(),inf); queue<ll> q; for(ll s:starts) if(dist[s]==inf){dist[s]=0; q.push(s);} while(!q.empty()){ ll v=q.front(); q.pop(); for(ll to:g[v]) if(dist[to]==inf){dist[to]=dist[v]+1; q.push(to);} } return dist; }
vl dijkstra(const graph& g,ll s){return dijkstra(g,vl{s});}
vl dijkstra(const graph& g,initializer_list<ll> starts){return dijkstra(g,vl(starts));}
vl dijkstra(const Graph& g,const vl& starts){ vl dist(g.size(),inf); rpq<pll> q; for(ll s:starts) if(dist[s]==inf){dist[s]=0; q.push({0,s});} while(!q.empty()){ auto [d,v]=q.top(); q.pop(); if(d!=dist[v]) continue; for(auto [to,w]:g[v]){ if(w>=inf-d) continue; ll nd=d+w; if(nd<dist[to]){dist[to]=nd; q.push({nd,to});} } } return dist; }
vl dijkstra(const Graph& g,ll s){return dijkstra(g,vl{s});}
vl dijkstra(const Graph& g,initializer_list<ll> starts){return dijkstra(g,vl(starts));}
const vl Pow2={1LL,2LL,4LL,8LL,16LL,32LL,64LL,128LL,256LL,512LL,1024LL,2048LL,4096LL,8192LL,16384LL,32768LL,65536LL,131072LL,262144LL,524288LL,1048576LL,2097152LL,4194304LL,8388608LL,16777216LL,33554432LL,67108864LL,134217728LL,268435456LL,536870912LL,1073741824LL,2147483648LL,4294967296LL,8589934592LL,17179869184LL,34359738368LL,68719476736LL,137438953472LL,274877906944LL,549755813888LL,1099511627776LL,2199023255552LL,4398046511104LL,8796093022208LL,17592186044416LL,35184372088832LL,70368744177664LL,140737488355328LL,281474976710656LL,562949953421312LL,1125899906842624LL,2251799813685248LL,4503599627370496LL,9007199254740992LL,18014398509481984LL,36028797018963968LL,72057594037927936LL,144115188075855872LL,288230376151711744LL,576460752303423488LL,1152921504606846976LL};

vl dx={0,1,0,-1}, dy={1,0,-1,0};
vl dx8={1,1,0,-1,-1,-1,0,1}, dy8={0,1,1,1,0,-1,-1,-1}; // 8近傍

vector<mint> fac,finv,pow2;
void factorial(ll N=1000000LL){ll M=N+100; fac.assign(M+1,1); finv.assign(M+1,1); pow2.assign(M+1,1); rep1(i,M) fac[i]=fac[i-1]*i; finv[M]=fac[M].inv(); for(ll i=M;i>=1;i--) finv[i-1]=finv[i]*i; rep1(i,M) pow2[i]=pow2[i-1]*2;} // N+100まで階乗・逆階乗・2の累乗前計算
void ensure_factorial(ll N){if((ll)fac.size()>N) return; factorial(N);} // 階乗表の不足分確保
mint nCr(ll N,ll r){if(N<0||r<0||N<r) return 0; ensure_factorial(N); return fac[N]*finv[r]*finv[N-r];} // 二項係数
mint nPr(ll N,ll r){if(N<0||r<0||N<r) return 0; ensure_factorial(N); return fac[N]*finv[N-r];} // 順列数
// https://github.com/yuki-4869/Algorithm/blob/main/DataStructureBasic/range_set.cpp
template<class T = long long, class Count = T>
class RangeSet {
    static_assert(std::is_integral_v<T> && std::is_signed_v<T> && sizeof(T) <= 8);
    static_assert((std::is_integral_v<Count> && !std::is_same_v<Count, bool> && sizeof(Count) <= 8)
                  || std::is_same_v<Count, __int128_t>);

public:
    using value_type = T;
    using count_type = Count;
    using ptt = std::pair<T, T>;
    using const_iterator = typename std::map<T, T>::const_iterator;

    static constexpr T TINF = std::numeric_limits<T>::max() / 2;

private:
    using wide_type = __int128_t;
    std::map<T, T> ranges_;
    Count total_ = 0;
    static wide_type length(T l, T r) {
        return static_cast<wide_type>(r) - static_cast<wide_type>(l);
    }
    static Count checked_count(wide_type value) {
        if (value > static_cast<wide_type>(std::numeric_limits<Count>::max()))
            std::abort();
        return static_cast<Count>(value);
    }

public:
    RangeSet() = default;
    RangeSet(std::initializer_list<ptt> ranges) {
        for (auto [l, r] : ranges) insert(l, r);
    }
    RangeSet(const RangeSet&) = default;
    RangeSet& operator=(const RangeSet&) = default;
    RangeSet(RangeSet&& other) noexcept
        : ranges_(std::move(other.ranges_)), total_(std::exchange(other.total_, 0)) {
        other.ranges_.clear();
    }
    RangeSet& operator=(RangeSet&& other) noexcept {
        if (this != &other) {
            ranges_ = std::move(other.ranges_);
            total_ = std::exchange(other.total_, 0);
            other.ranges_.clear();
        }
        return *this;
    }

    std::optional<ptt> covering_interval(T x) const {
        auto it = ranges_.upper_bound(x);
        if (it == ranges_.begin()) return std::nullopt;
        --it;
        if (x < it->second) return ptt{it->first, it->second};
        return std::nullopt;
    }

    std::optional<ptt> covering_interval(T l, T r) const {
        if (l >= r) return ptt{l, l};
        auto interval = covering_interval(l);
        if (interval && r <= interval->second) return interval;
        return std::nullopt;
    }
    bool covered(T l, T r) const { return covering_interval(l, r).has_value(); }
    bool covered(T x) const { return covering_interval(x).has_value(); }
    bool contains(T x) const { return covered(x); }

    ptt covered_by(T l, T r) const {
        if (l >= r) return {0, 0};
        return covering_interval(l, r).value_or(ptt{-TINF, -TINF});
    }
    bool overlaps(T l, T r) const {
        if (l >= r) return false;
        auto it = ranges_.lower_bound(l);
        if (it != ranges_.end() && it->first < r) return true;
        return it != ranges_.begin() && std::prev(it)->second > l;
    }

    Count insert(T l, T r) {
        if (l >= r) return 0;
        auto first = ranges_.lower_bound(l);
        if (first != ranges_.begin() && std::prev(first)->second >= l) --first;
        auto last = first;
        T merged_l = l, merged_r = r;
        wide_type old_length = 0;
        while (last != ranges_.end() && last->first <= merged_r) {
            merged_l = std::min(merged_l, last->first);
            merged_r = std::max(merged_r, last->second);
            old_length += length(last->first, last->second);
            ++last;
        }
        const wide_type added = length(merged_l, merged_r) - old_length;
        const Count next_total = checked_count(static_cast<wide_type>(total_) + added);
        if (first == last) {
            ranges_.emplace_hint(last, merged_l, merged_r);
        } else {
            auto rest = std::next(first);
            auto node = ranges_.extract(first);
            ranges_.erase(rest, last);
            node.key() = merged_l;
            node.mapped() = merged_r;
            ranges_.insert(last, std::move(node));
        }
        total_ = next_total;
        return static_cast<Count>(added);
    }
    Count insert(T x) {
        if (x == std::numeric_limits<T>::max())
            std::abort();
        return insert(x, static_cast<T>(x + 1));
    }

    Count erase(T l, T r) {
        if (l >= r) return 0;
        auto it = ranges_.lower_bound(l);
        if (it != ranges_.begin() && std::prev(it)->second > l) --it;
        wide_type removed = 0;
        while (it != ranges_.end() && it->first < r) {
            const T a = it->first, b = it->second;
            removed += length(std::max(a, l), std::min(b, r));
            if (a < l) {
                if (r < b) {
                    ranges_.emplace(r, b);
                    it->second = l;
                    break;
                }
                it->second = l;
                ++it;
            } else if (b <= r) {
                it = ranges_.erase(it);
            } else {
                auto next = std::next(it);
                auto node = ranges_.extract(it);
                node.key() = r;
                ranges_.insert(next, std::move(node));
                break;
            }
        }
        total_ = static_cast<Count>(static_cast<wide_type>(total_) - removed);
        return static_cast<Count>(removed);
    }
    Count erase(T x) {
        if (x == std::numeric_limits<T>::max()) return 0;
        return erase(x, static_cast<T>(x + 1));
    }

    T mex(T x = 0) const {
        auto interval = covering_interval(x);
        return interval ? interval->second : x;
    }
    Count count_covered(T l, T r) const {
        if (l >= r) return 0;
        auto it = ranges_.lower_bound(l);
        if (it != ranges_.begin() && std::prev(it)->second > l) --it;
        wide_type count = 0;
        while (it != ranges_.end() && it->first < r) {
            count += length(std::max(l, it->first), std::min(r, it->second));
            ++it;
        }
        return static_cast<Count>(count);
    }

    Count cover_length() const { return total_; }
    std::size_t size() const { return ranges_.size(); }
    bool empty() const { return ranges_.empty(); }
    void clear() { ranges_.clear(); total_ = 0; }
    void swap(RangeSet& other) noexcept {
        ranges_.swap(other.ranges_);
        std::swap(total_, other.total_);
    }
    std::vector<ptt> intervals() const { return {ranges_.begin(), ranges_.end()}; }
    const_iterator begin() const { return ranges_.cbegin(); }
    const_iterator end() const { return ranges_.cend(); }
    void output() const {
        std::cout << "RangeSet: ";
        for (auto [l, r] : ranges_) std::cout << '[' << +l << ',' << +r << ") ";
        std::cout << '\n';
    }
};

/*
細かい注意点
整数座標の集合。区間は半開区間[l,r)。Tは座標、Countは個数の型(既定long long)。
ptt=pair<T,T>。K/K2はrs/otherの操作前の区間数、Mは初期区間数、Dは走査・統合・削除する区間数。
Tは64bit以下の符号付き整数。Countはbool以外の64bit以下の整数または__int128_t。
Tの最大値は格納不可。insert(最大値)や総被覆数のCount超過はメッセージなしで停止。
erase(最大値)は0。大きな被覆数にはRangeSet<ll,__int128_t>を使う。
l>=rではinsert/erase/count_coveredは0、coveredはtrue、overlapsはfalse。
空区間のcovering_interval(l,r)は{l,l}、covered_by(l,r)は{0,0}。
size()は保持区間数、cover_length()は被覆された整数の個数。
列挙は左端昇順の読み取り専用。走査中に集合を更新しない。intervals()は独立なコピー。
TINFはcovered_byの互換返り値用。座標制限や内部番兵ではない。
空ならbegin()==end()。解放O(K)。output()は明示呼び出し時だけ標準出力する。

使える関数一覧
// 構築・コピー・ムーブ(コンストラクタには返り値はない)
RangeSet<T, Count> rs;                        // 空集合で初期化 O(1)
RangeSet<T, Count> rs{{a,b},{c,d}};           // M個の区間から構築、重複・隣接を統合 O(M log M)
RangeSet<T, Count> rs(other);                 // 独立なコピーを構築 O(K2)
RangeSet<T, Count> rs(std::move(other));      // 集合を移し、otherを空にする O(1)
rs = other;                                   // RangeSet&: rsへの参照。独立なコピーで上書き O(K+K2)
rs = std::move(other);                        // RangeSet&: rsへの参照。集合を移し、otherを空にする O(K)

// 追加・削除
rs.insert(l,r);                               // Count: [l,r)を追加し、新たに被覆した個数を返す O(log K+D)
rs.insert(x);                                 // Count: 1点xを追加し、新たに被覆した個数(0か1)を返す O(log K)
rs.erase(l,r);                                // Count: [l,r)を削除し、実際に削除した個数を返す O(log K+D)
rs.erase(x);                                  // Count: 1点xを削除し、実際に削除した個数(0か1)を返す O(log K)

// 被覆・重なりの判定
rs.covered(l,r);                              // bool: [l,r)全体が被覆されていればtrue O(log K)
rs.covered(x);                                // bool: 1点xが被覆されていればtrue O(log K)
rs.contains(x);                               // bool: covered(x)と同じ O(log K)
rs.overlaps(l,r);                             // bool: [l,r)に被覆された整数が1つ以上あればtrue O(log K)

// 保持区間の取得
rs.covering_interval(x);                      // optional<ptt>: xを含む保持区間、なければnullopt O(log K)
rs.covering_interval(l,r);                    // optional<ptt>: [l,r)全体を含む保持区間、なければnullopt O(log K)
rs.covered_by(l,r);                           // ptt: 包含する保持区間、なければ{-TINF,-TINF} O(log K)

// mex・個数・状態
rs.mex(x);                                    // T: x以上の未被覆の整数のうち最小のものを返す O(log K)
rs.mex();                                     // T: 0以上の未被覆の整数のうち最小のものを返す O(log K)
rs.count_covered(l,r);                        // Count: [l,r)内で被覆された整数の個数を返す O(log K+D)、最悪O(K)
rs.cover_length();                            // Count: 集合全体で被覆された整数の個数を返す O(1)
rs.size();                                    // size_t: 保持する区間数を返す(整数の個数ではない) O(1)
rs.empty();                                   // bool: 空集合ならtrue O(1)
rs.clear();                                   // void: 全区間を削除し、総被覆数も0にする O(K)
rs.swap(other);                               // void: otherと区間集合・総被覆数を交換 O(1)

// 区間の列挙・表示
rs.intervals();                               // vector<ptt>: 左端の昇順で全保持区間のコピーを返す O(K)、追加メモリO(K)
rs.begin();                                   // const_iterator: 最初の区間を指すイテレータを返す O(1)
rs.end();                                     // const_iterator: 最後の区間の次を指すイテレータを返す O(1)
for (auto [l,r] : rs) { ... }                 // 読み取り専用で全区間を左端の昇順に走査 O(K)
rs.output();                                  // void: "RangeSet: [l,r) ..."形式で全区間を標準出力 O(K)

基本の関数
RangeSet<ll> rs;                              // 空集合
rs.insert(1,10);                              // [1,10)を追加
rs.erase(3,7);                                // [3,7)を削除
auto covered = rs.covered(1,3);               // true
auto mex = rs.mex(1);                         // 3
auto count = rs.cover_length();               // 5
*/

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    ll n;
    cin >> n;
    auto a = cin_vl(n);

    ll ans = 0;
    RangeSet<ll> rs;
    rep(i,n){
        if(rs.covered(a[i])){
            auto itr = rs.covered_by(a[i],a[i]+1);
            
            auto[l,r] = itr;

            //p2(l,r);
            ans += (a[i]-l+1)*(r-a[i]);

            ll y = l+r-1-a[i];
            rs.erase(l,r);
            rs.insert(l-1,y);
            rs.insert(y+1,r+1);
        }
        else rs.insert(a[i],a[i]+1);
    }

    p(ans);
}
0