#include <bits/stdc++.h>
using namespace std;

using ii = pair<int, int>;

vector<int> lis(vector<int> v){
	int n = v.size();
	vector<int> vec = {0};
	vector<int> res(n, 0);

	for (int i = 0; i < n; i++){
		if (v[i] > vec.back()){
			res[i] = vec.size();
			vec.push_back(v[i]);
		}
		else{
			int pos = lower_bound(vec.begin(), vec.end(), v[i]) - vec.begin();
			res[i] = pos;
			vec[pos] = v[i];
		}
	}

	return res;
}

vector<int> lds(vector<int> v){
	reverse(v.begin(), v.end());
	vector<int> res = lis(v);
	reverse(res.begin(), res.end());
	return res;
}

vector<ii> min_shooting_buildings(vector<int> A){
	if ((int)A.size() == 0) return {};
	if ((int)A.size() == 1) return {{A[0], A[0]}};

	int n = A.size();

	vector<int> len = lds(A);
	vector<int> valid;

	// cout << "A: ";
	// for (int i = 0; i < n; i++){
	// 	cout << A[i] << " \n"[i == n-1];
	// }
	// cout << "len: ";
	// for (int i = 0; i < n; i++){
	// 	cout << len[i] << " \n"[i == n-1];
	// }

	int mx = -1;
	for (int i = 0; i < n; i++){
		if (A[i] <= mx) continue;
		valid.push_back(i);
		mx = max(mx, A[i]);
	}

	sort(valid.begin(), valid.end(), [&](int x, int y){
		if (len[x] == len[y]) return x > y;
		return len[x] > len[y];
	});

	if ((int)valid.size() == 1){
		vector<ii> res = {{A[valid[0]], A[valid[0]]}};
		A.erase(A.begin() + valid[0]);
		vector<ii> recur = min_shooting_buildings(A);
		res.insert(res.end(), recur.begin(), recur.end());
		return res;
	}
	else{
		if (valid[0] > valid[1]) swap(valid[0], valid[1]);
		vector<ii> res = {{A[valid[0]], A[valid[1]]}};
		A.erase(A.begin() + valid[1]);
		A.erase(A.begin() + valid[0]);
		vector<ii> recur = min_shooting_buildings(A);
		res.insert(res.end(), recur.begin(), recur.end());
		return res;
	}
}