/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;
const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;
template<class T>
struct fenwick_tree_max{
int n;
vector<T> data;
T T_id;
fenwick_tree_max(int n, T init, T T_id = numeric_limits<T>::min()): fenwick_tree_max(vector<T>(n, init), T_id){ }
fenwick_tree_max(const vector<T> &v, T T_id = numeric_limits<T>::min()): n((int)v.size()), data(v), T_id(T_id){
for(auto i = 1; i <= n; ++ i) if(i + (i & -i) <= n) data[i + (i & -i) - 1] = max(data[i + (i & -i) - 1], data[i - 1]);
}
// O(log n)
void update(int p, T x){
assert(0 <= p && p < n);
for(++ p; p <= n; p += p & -p) data[p - 1] = max(data[p - 1], x);
}
// O(log n)
T pref(int r) const{
T s = T_id;
for(; r > 0; r -= r & -r) s = max(s, data[r - 1]);
return s;
}
// pred(sum[0, r)) is T, T, ..., T, F, F, ..., F, returns max r with T
// O(log n)
int max_pref(auto pred) const{
assert(pred(T_id));
int p = 0;
T pref = T_id;
for(auto i = __lg(n + 1); i >= 0; -- i) if(p + (1 << i) <= n && pred(max(pref, data[p + (1 << i) - 1]))){
pref = max(pref, data[p + (1 << i) - 1]);
p += 1 << i;
}
return p;
}
};
const int MAXT = 270000;
struct seg2
{
pair<int, int> tree[MAXT];
int lim;
void init(int n)
{
fill(tree, tree + MAXT, pair<int, int>(-1e9, -1e9));
for (lim = 1; lim <= n; lim <<= 1);
}
void upd(int x, pair<int, int> v)
{
x += lim;
tree[x] = v;
while (x > 1)
{
x >>= 1;
tree[x] = max(tree[2 * x], tree[2 * x + 1]);
}
}
pair<int, int> query(int s, int e)
{
s += lim;
e += lim;
pair<int, int> ret(-1e9, -1e9);
while (s < e)
{
if (s % 2 == 1) ret = max(ret, tree[s++]);
if (e % 2 == 0) ret = max(ret, tree[e--]);
s >>= 1, e >>= 1;
}
if (s == e) ret = max(ret, tree[s]);
return ret;
}
} seg2;
vector<pair<int, int>> min_shooting_buildings(vector<int> a) {
int n = isz(a);
vector<int> dp(n);
fenwick_tree_max<int> fenw(n, -1e9);
vector<vector<int>> dpval, N(n);
for (int i = n - 1; i >= 0; --i) {
int val = max(0, fenw.pref(a[i]) + 1);
dp[a[i] - 1] = val; fenw.update(a[i] - 1, val);
if (val >= isz(dpval)) dpval.resize(val + 1);
dpval[val].emplace_back(i);
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (a[i] > a[j] and dp[i] + 1 == dp[j]) N[j].emplace_back(i);
}
}
int cntt = 0;
vector<int> rev = {-1};
vector<int> ord(n);
for (auto &v : dpval) {
for (int val : v) {
// cout << val << ": ";
// for (int idx : N[val]) cout << idx << " ";
sort(all(N[val]), [&](int x, int y) {
return ord[x] > ord[y];
});
// cout << endl;
}
sort(all(v), [&](int x, int y) {
// cout << "cmp: " << x << " " << y << endl;
for (int i = 0; i < min(isz(N[x]), isz(N[y])); ++i) if (N[x][i] != N[y][i]) {
// cout << N[x][i] << " " << N[y][i] << endl;
return (ord[N[x][i]] < ord[N[y][i]]);
}
if (isz(N[x]) != isz(N[y])) return isz(N[x]) > isz(N[y]);
// cout << isz(N[x]) << " " << isz(N[y]) << endl;
return (x > y);
});
for (int val : v) {
rev.push_back(val);
// cout << val << " ";
}
// cout << endl;
for (int val : v) ord[val] = ++cntt;
}
// for (int i = 0; i < n; ++i) cout << i << " " << ord[i] << endl;
vector<int> proc(n);
iota(all(proc), 0);
sort(all(proc), [&](int x, int y) { return ord[x] > ord[y]; });
vector<pair<int, int>> ans;
vector<int> killed(n);
int cnt = 0;
set<int> s, ord_s;
{
seg2.init(n);
int curMax = -1;
for (int j = 0; j < n; j++)
{
seg2.upd(j, pair<int, int>(a[j], j));
if (curMax < a[j])
{
s.insert(j);
ord_s.insert(ord[j]);
curMax = a[j];
}
}
}
auto Erase = [&](int x)
{
// cout << "Erase: " << x << endl;
auto nxt = s.upper_bound(x);
int y = (nxt == s.end() ? n : *nxt);
s.erase(x); ord_s.erase(ord[x]);
seg2.upd(x, pair<int, int>(-1e9, x));
while (y > 0)
{
auto val = seg2.query(0, y - 1);
if (s.find(val.second) != s.end()) break;
if (val.first < 0) break;
s.insert(val.second);
ord_s.insert(ord[val.second]);
y = val.second;
}
};
while (cnt < n)
{
// cout << cnt << " " << isz(s) << endl;
if (isz(s) == 1)
{
cnt++;
int nd = rev[*ord_s.begin()];
Erase(nd);
ans.emplace_back(a[nd], n);
}
else
{
cnt += 2;
auto it = ord_s.end();
int nd1 = rev[*--it];
int nd2 = rev[*--it];
Erase(nd1);
Erase(nd2);
ans.emplace_back(a[nd1], a[nd2]);
}
}
// cout << -1 << endl;
return ans;
}
void solve() {
int n;
cin >> n;
assert(n <= 500);
vector<int> a(n);
for (auto &val : a) cin >> val;
auto res = min_shooting_buildings(a);
cout << res.size() << '\n';
for (auto [u, v] : res) cout << u << " " << v << "\n";
}
signed main() {
#ifndef CDuongg
if(fopen(taskname".inp", "r"))
assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
auto start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; //cin >> t;
while(t--) solve();
#ifdef CDuongg
auto end = chrono::high_resolution_clock::now();
cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
cout << "Check array size pls sir" << endl;
#endif
}