#pragma GCC target("avx,avx2")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,tune=native")
#pragma GCC optimize("03")

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <bitset>
#include <stack>
#include <random>

#define pb push_back
#define ll long long
#define ld long double
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()

using namespace std;

//tg: @galebickosikasa

const int maxn = (int)3e5;
const int inf = (int)2e9;
const ld eps = 1e-9;
mt19937 SuperRandom;

struct SparseTable{
    vector<vector<pair<int, int>>> st;
    vector<int> pow;

    SparseTable(const vector<int>& v){
        int j = 1;
        while (1<<j < sz(v)) ++j;
        st = vector<vector<pair<int, int>>> (j, vector<pair<int, int>> (sz(v)));
        pow = vector<int> (sz(v) + 1);
        int tmp = 0;
        for (int i = 0; i < sz(v); ++i){
            st[0][i].first = st[0][i].second = v[i];
            if (1<<(tmp + 1) <= i) ++tmp;
            pow[i] = tmp;
        }
        pow[sz(v)] = j - 1;
        for (int k = 1; k < j; ++k){
            for (int i = 0; i < sz(v); ++i){
                st[k][i].first = max(st[k - 1][i].first, st[k - 1][i + (1<<(k - 1))].first);
                st[k][i].second = max(st[k - 1][i].second, st[k - 1][i + (1<<(k - 1))].second);
            }
        }
    }

    pair<int, int> get(int l, int r) const {
        if (l > r) swap(l, r);
        int k = pow[r - l + 1];
        return {max(st[k][l].first, st[k][r - (1<<k) + 1].first), min(st[k][l].second, st[k][r - (1<<k) + 1].second)};
    }

};

int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> goo(n);
    for (auto& x: goo) cin >> x;



}