#ifdef NACHIA #define _GLIBCXX_DEBUG #else // disable assert #define NDEBUG #endif #include #include #include #include using namespace std; using ll = long long; const ll INF = 1ll << 60; #define REP(i,n) for(ll i=0; i using V = vector; template void chmax(A& l, const B& r){ if(l < r) l = r; } template void chmin(A& l, const B& r){ if(r < l) l = r; } using ull = unsigned long long; ull wt(V a){ ull s = 0, ans = 0; for(ll x : a){ ans += s * ull(x); s += x; } return ans; } template Int FloorDiv(Int a, Int b){ if(b < Int(0)){ a = -a; b = -b; } if(a >= Int(0) || a % b == Int(0)) return a / b; return a / b - Int(1); } void testcase(){ ll N; cin >> N; V A(N); REP(i,N) cin >> A[i]; sort(A.begin(), A.end()); V> st; for(ll a : A){ ll l = a, r = a + 2, sz = 1, sum = a; while(st.size() && l < get<1>(st.back())){ sz += get<2>(st.back()); sum += get<3>(st.back()); l = FloorDiv(sum - sz * (sz - 1) / 2, sz); r = l + sz + 1; st.pop_back(); } st.push_back({ l, r, sz, sum }); } V B; for(auto [l,r,sz,sum] : st){ // cout << l << " " << r << " " << sz << " " << sum << endl; ll ab = (l + r - 1) * (r - l) / 2 - sum; for(ll i=l; isync_with_stdio(0); testcase(); return 0; }