#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Int = long long; template ostream &operator<<(ostream &os, const vector &as); template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template ostream &operator<<(ostream &os, const vector &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; } template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } #define COLOR(s) ("\x1b[" s "m") #define l first #define r second constexpr Int INF = 1001001001001001001LL; int N; vector A; int main() { for (; ~scanf("%d", &N); ) { A.resize(N); for (int i = 0; i < N; ++i) scanf("%lld", &A[i]); sort(A.begin(), A.end()); set> fs; fs.emplace(-INF, -INF); fs.emplace(+INF, +INF); auto add = [&](Int l, Int r) -> void { auto it = fs.lower_bound(make_pair(l, r)); if (r + 1 == it->first) { r = it->second; it = fs.erase(it); } --it; if (it->second == l - 1) { l = it->first; it = fs.erase(it); } fs.emplace(l, r); }; for (const Int a : A) { auto it = fs.lower_bound(make_pair(a, +INF)); --it; const Int l = it->first; const Int r = it->second; if (l <= a && a <= r) { const Int b = l + r - a; fs.erase(it); add(l - 1, b - 1); add(b + 1, r + 1); } else { add(a, a); } // cerr<