// @EXPECTED_RESULTS@: TIME_LIMIT_EXCEEDED, WRONG_ANSWER
// WORK IN PROGRESS

#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;

struct interval { // [a,b]
	ll a;
	ll b; // inclusive
	ll n;
	ll csum = 0;
	std::vector<ll> c; // unsorted
};

// join to A
void join(interval &A, interval &B) {
	A.n += B.n;
	A.csum += B.csum;
	for(ll c : B.c) {
		A.c.push_back(c);
	}
}

void reoptimize(interval &A) {
	ll n = A.n;
	A.a = round((A.csum - (n*(n-1))/2)/double(n));
	A.b = A.a+n-1;
}

int main() {

	int n;
	cin >> n;

	std::vector<ll> x(n);
	for(int i = 0; i < n; i++)
		cin >> x[i];

	set<pair<ll,size_t>> intervals_a;
	std::vector<interval> intervals;

	for(int i = 0; i < n; i++) {
		// check if in existing interval
		ll c = x[i];
		auto l = lower_bound(intervals_a.begin(), intervals_a.end(), pair<ll,size_t>{c, 1e9+1});
		if(l != intervals_a.end()) {
			interval* in = &intervals[(*l).second];
			if(in->b >= c) {
				// append to interval and reoptimize
				in->n++;
				in->csum+=c;
				in->c.push_back(c);
				reoptimize(*in);

				// update set
				size_t index = (*l).second;
				intervals_a.erase(l);
				intervals_a.insert({in->a, index});

				// make joining while loop
			}
		} else { // new interval
			intervals.push_back({c,c,1,c,{c}});
			intervals_a.insert({c,intervals.size()-1});
		}

	}

}