#line 1 "a.cpp" // https://qandori.github.io/cp-library/ // #include #include using namespace std; using std::cin, std::cout, std::cerr; #define vec vector typedef long double ld; #if LONG_MAX == 2147483647L #undef long #define long long long #endif #define uint unsigned int #define ulong unsigned long #define overload3(a, b, c, name, ...) name #define rep3(i, a, b) for (int i = (a); i < (b); i++) #define rep2(i, n) rep3(i, 0, n) #define rep1(n) rep2(__i__, n) #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define per3(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define per2(i, n) per3(i, 0, n) #define per1(n) per2(__i__, n) #define per(...) overload3(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__) #define CP_ALL_SELECT(first, ...) first #define CP_ALL_RANGE(a) std::begin(a), std::end(a) #define all(...) CP_ALL_SELECT(__VA_OPT__(CP_ALL_RANGE, ) all)(__VA_ARGS__) #define UNIQUE(a) sort(all(a)), a.erase(unique(all(a)), a.end()), a.shrink_to_fit() #define sz(a) static_cast(a.size()) #ifndef DEBUG #define cerr \ if (false) cerr #undef endl #define endl '\n' #endif inline auto operator^=(vector::reference a, bool b) noexcept { if (b) a.flip(); return a; } inline auto operator&=(vector::reference a, bool b) noexcept { if (!b) a = false; return a; } inline auto operator|=(vector::reference a, bool b) noexcept { if (b) a = true; return a; } inline ostream &operator<<(ostream &os, __int128_t value) { ostream::sentry s(os); if (s) { __uint128_t tmp = value; if (value < 0) tmp = -tmp; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) --d, *d = '-'; const int len = std::end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) os.setstate(std::ios_base::badbit); } return os; } template ostream &operator<<(ostream &os, pair a) { return os << a.first << ' ' << a.second; }; template ostream &operator<<(ostream &os, vector a) { const int n = a.size(); rep(i, n) { os << a[i]; if (i + 1 != n) os << " "; } return os; } template istream &operator>>(istream &is, pair &a) { return is >> a.first >> a.second; } template ostream &operator<<(ostream &os, array a) { rep(i, n) { os << a[i]; if (i + 1 != n) os << " "; } return os; } template istream &operator>>(istream &is, vector &a) { for (T &i : a) is >> i; return is; } template bool chmin(T &x, S y) { if ((T)y < x) { x = (T)y; return true; } return false; } template bool chmax(T &x, S y) { if (x < (T)y) { x = (T)y; return true; } return false; } template void operator++(vector &a) { for (T &i : a) ++i; } template void operator--(vector &a) { for (T &i : a) --i; } template void operator++(vector &a, int) { for (T &i : a) i++; } template void operator--(vector &a, int) { for (T &i : a) i--; } void init(), solve(); int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); cerr << fixed << setprecision(20); init(); int t = 1; // cin >> t; while (t--) solve(); } // #define COMB_MAX 1e6 // #include "lib/math/comb.hpp" // #include "lib/fps/fps.hpp" // #include "lib/math/mint.hpp" void init() {} #line 1 "lib/data_structure/interval_set.hpp" #line 8 "lib/data_structure/interval_set.hpp" #include #line 12 "lib/data_structure/interval_set.hpp" #include #include #line 16 "lib/data_structure/interval_set.hpp" template && sizeof(T) <= 8, std::uint64_t, std::conditional_t, __uint128_t, T>>> class IntervalSet { static_assert(std::numeric_limits::is_integer && !std::is_same_v); static_assert(std::numeric_limits::is_integer && !std::is_same_v); std::map ranges; Size total = 0; static Size length(const T &l, const T &r) { return static_cast(r) - static_cast(l); } public: using coordinate_type = T; using size_type = Size; using interval_type = std::pair; using const_iterator = typename std::map::const_iterator; using const_reverse_iterator = typename std::map::const_reverse_iterator; IntervalSet() = default; explicit IntervalSet(std::vector intervals) { assign(std::move(intervals)); } IntervalSet(std::initializer_list intervals) { assign(intervals); } IntervalSet(const IntervalSet &) = default; IntervalSet(IntervalSet &&other) noexcept(std::is_nothrow_constructible_v && std::is_nothrow_swappable_v) { swap(other); } IntervalSet &operator=(IntervalSet other) noexcept(std::is_nothrow_swappable_v) { swap(other); return *this; } void assign(std::vector intervals) { std::sort(intervals.begin(), intervals.end()); IntervalSet result; auto last = result.ranges.end(); for (auto [l, r] : intervals) { assert(l <= r); if (l == r) continue; if (last != result.ranges.end() && l <= last->second) { if (last->second < r) { result.total += length(last->second, r); last->second = r; } } else { last = result.ranges.emplace_hint(result.ranges.end(), l, r); result.total += length(l, r); } } swap(result); } size_type insert(T l, T r) { assert(l <= r); if (l == r) return 0; auto it = ranges.upper_bound(l); if (it != ranges.begin() && std::prev(it)->second >= l) --it; if (it == ranges.end() || it->first > r) { ranges.emplace_hint(it, l, r); auto added = length(l, r); total += added; return added; } if (it->first <= l && r <= it->second) return 0; T left = (std::min)(l, it->first), right = (std::max)(r, it->second); auto removed = length(it->first, it->second); auto next_it = std::next(it); while (next_it != ranges.end() && next_it->first <= right) { right = (std::max)(right, next_it->second); removed += length(next_it->first, next_it->second); next_it = ranges.erase(next_it); } if (left == it->first) it->second = right; else { auto node = ranges.extract(it); node.key() = left; node.mapped() = right; ranges.insert(next_it, std::move(node)); } size_type added = length(left, right) - removed; total += added; return added; } size_type insert(T x) { if constexpr (std::numeric_limits::is_bounded) assert(x < (std::numeric_limits::max)()); return insert(x, static_cast(x + 1)); } size_type erase(T l, T r) { assert(l <= r); if (l == r) return 0; auto it = ranges.upper_bound(l); if (it != ranges.begin() && std::prev(it)->second > l) --it; size_type removed = 0; if (it != ranges.end() && it->first < l) { T right = it->second; if (r < right) { ranges.emplace_hint(std::next(it), r, right); it->second = l; removed = length(l, r); total -= removed; return removed; } removed = length(l, right); it->second = l; ++it; } while (it != ranges.end() && it->first < r) { if (r < it->second) { removed += length(it->first, r); auto hint = std::next(it); auto node = ranges.extract(it); node.key() = r; ranges.insert(hint, std::move(node)); break; } removed += length(it->first, it->second); it = ranges.erase(it); } total -= removed; return removed; } size_type erase(T x) { if constexpr (std::numeric_limits::is_bounded) if (x == (std::numeric_limits::max)()) return 0; return erase(x, static_cast(x + 1)); } const_iterator find(T x) const { auto it = ranges.upper_bound(x); if (it == ranges.begin()) return ranges.end(); --it; return x < it->second ? it : ranges.end(); } const_iterator lower_bound(T x) const { auto it = ranges.upper_bound(x); if (it != ranges.begin() && x < std::prev(it)->second) --it; return it; } bool contains(T x) const { return find(x) != end(); } bool contains(T l, T r) const { assert(l <= r); if (l == r) return true; auto it = find(l); return it != end() && r <= it->second; } bool intersects(T l, T r) const { assert(l <= r); if (l == r) return false; auto it = lower_bound(l); return it != end() && it->first < r; } size_type count(T l, T r) const { assert(l <= r); if (l == r) return 0; size_type result = 0; for (auto it = lower_bound(l); it != end() && it->first < r; ++it) result += length((std::max)(l, it->first), (std::min)(r, it->second)); return result; } std::optional next(T x) const { auto it = lower_bound(x); if (it == end()) return std::nullopt; return (std::max)(x, it->first); } std::optional prev(T x) const { auto it = ranges.upper_bound(x); if (it == ranges.begin()) return std::nullopt; --it; return (std::min)(x, static_cast(it->second - 1)); } T mex(T x = 0) const { auto it = find(x); return it == end() ? x : it->second; } std::optional min() const { if (empty()) return std::nullopt; return begin()->first; } std::optional max() const { if (empty()) return std::nullopt; return static_cast(ranges.rbegin()->second - 1); } size_type size() const { return total; } std::size_t interval_count() const { return ranges.size(); } bool empty() const { return ranges.empty(); } const_iterator begin() const { return ranges.begin(); } const_iterator end() const { return ranges.end(); } const_reverse_iterator rbegin() const { return ranges.rbegin(); } const_reverse_iterator rend() const { return ranges.rend(); } void clear() { ranges.clear(); total = 0; } void swap(IntervalSet &other) noexcept(std::is_nothrow_swappable_v) { ranges.swap(other.ranges); using std::swap; swap(total, other.total); } friend void swap(IntervalSet &a, IntervalSet &b) noexcept(noexcept(a.swap(b))) { a.swap(b); } }; #line 143 "a.cpp" void solve() { int n; cin >> n; IntervalSet s; long ans = 0; rep(i, n) { long x; cin >> x; if (!s.contains(x)) { s.insert(x); continue; } auto [l, r] = *s.lower_bound(x); r--; const long ll = x - l, rr = r - x; ans += (ll + 1) * (rr + 1); s.insert(l - 1), s.insert(r + 1); s.erase(x + rr - ll); } cout << ans << endl; }