#pragma GCC optimize "trapv"
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define ld long double
// #define mp make_pair
#define pii pair<int,int>
// #define mod 998244353
#define rep(i,n) for(int i=0;i<n;i++)
#define repp(i,a,n) for(int i=a;i<n;i++)
#define all(v) v.begin(),v.end()
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>//s.order_of_key(val) *s.find_by_order(ind)
#define random(l,r,T)    uniform_int_distribution<T>(l,r)(rng)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//----------------------------------- DEBUG -----------------------------------
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }
 
//----------------------------------- END DEBUG --------------------------------
template<typename T_vector>
void output_vector(const T_vector &v, bool add_one = false, int start = -1, int end = -1) {
    if (start < 0) start = 0;
    if (end < 0) end = int(v.size());
 
    for (int i = start; i < end; i++)
        cout << v[i] + (add_one ? 1 : 0) << (i < end - 1 ? ' ' : ' ');
}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://x...content-available-to-author-only...i.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<typename T> istream& operator >>(istream &in,vector<T> &v){
    for(auto &x:v) in>>x; return in;
}
template<typename T> ostream& operator <<(ostream &out,vector<T> &v){
    for(auto &x:v) out<<x<<' '; return out;
}
template<typename T1,typename T2> istream& operator >>(istream &in,pair<T1,T2> &p){
    in>>p.first>>p.second; return in;
}
template<typename T1,typename T2> ostream& operator <<(ostream &out,pair<T1,T2> &p){
    out<<p.first<<' '<<p.second; return out;
}
template<class T, class H>using umap=unordered_map<T,H,custom_hash>;
template<class T>using uset=unordered_set<T,custom_hash>;
const ll MaxN = 2e5 + 5;
vector<pair<ll,ll>> st(4 * MaxN, {LLONG_MAX, -1});
pair<ll,ll> merge(pair<ll,ll> p1, pair<ll,ll> p2) {
    return (p1 < p2) ? p1 : p2;
}
void build(ll node, ll start, ll end, vll &a)
{
    if(start == end)
    {
        st[node] = {a[end], end};
    }
    else
    {
        ll mid = (start + end) / 2;
        build(2 * node + 1, start, mid, a);
        build(2 * node + 2, mid + 1, end, a);
        st[node] = merge(st[2 * node + 1], st[2 * node + 2]);
    }
}
pair<ll,ll> query(ll node, ll start, ll end, ll l, ll r)
{
    if(r < start || l > end)
    return {LLONG_MAX, -1};
    if(start >= l && end <= r)
    return st[node];
    ll mid = (start + end) / 2;
    return merge(query(2 * node + 1, start, mid, l, r), query(2 * node + 2, mid + 1, end, l, r));
}
void update(ll node, ll start, ll end, ll pos, ll val)
{
    if(pos < start || pos > end)
    return;
    else if(start == pos && end == pos)
    {
        st[node] = {val, pos};
        return;
    }
    ll mid = (start + end) / 2;
    update(2 * node + 1, start, mid, pos, val);
    update(2 * node + 2, mid + 1, end, pos, val);
    st[node] = merge(st[2 * node + 1], st[2 * node + 2]);
}
int32_t main()
{
    #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif
    fio;
    clock_t clk = clock();
    int t = 1;
    // cin >> t;
    rep(tc, t)
    {
        // cout << "Case #" << tc + 1 << ": ";
        ll n;
        cin >> n;
        vll a(n);
        cin >> a;
        build(0, 0, n - 1, a);
        for(int i = 0; i < n - 1; i++) {
            auto minVal = query(0, 0, n - 1, i, n - 1);
            cout << minVal << endl;
            ll x = a[i];
            ll y = minVal.second;
            swap(a[i], a[y]);
            cout << a << endl;
            update(0, 0, n - 1, y, x);
        }
        cout << a << endl;
    } 
    cerr << '\n'<<"Time (in s): " << double(clock() - clk) * 1.0 / CLOCKS_PER_SEC << '\n';    
}