CF D 1

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int,int>
#define vec vector
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
void cv(vector <int> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvl(vector <ll> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}


void cvv(vector <vector <int> > &v){
    for (auto x: v) cv(x);
    cout<<"\n";
}

void cvb(vector <bool> v){
    for (bool x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvs(vector <string>  v){
    for (auto a: v){
        cout<<a<<"\n";
    }
}

void cvp(vector <pii> a){
    for (auto p: a){
        cout<<p.first<<' '<<p.second<<"\n";
    }
    cout<<"\n";
}

bool sh=1;


int n,N,k;

vector <int> a;

const int inf = 1e9;

int up2(int x){
    int y = log2(x);
    if (pow(2, y) < x){
        y++;
    }
    y = pow(2, y);
    return y;
}

void seep(pii p){
    cout<<"("<<p.first<<","<<p.second<<") ";
}

struct tree{
    vector <pii> MN; //{mn, id}
    vector <pii> fr0, fr1; //макс мин на отрезках длины 2 {max mn, id}
    void bld(){
        N = up2(n);
        MN.assign(2 * N - 1, {inf,-1});
        for (int i = N - 1; i < N - 1 + n; ++i){
            int id = i - ( N - 1);
            MN[i] = {a[id], id};
        }
        for (int i = N - 2;i >= 0; --i){
            if (MN[2*i + 1] < MN[2 * i + 2]){
                MN[i] = MN[2*i + 1];
            }
            else{
                MN[i] = MN[2 * i + 2];
            }
        }

        fr0.assign(N - 1, {0,-1});
        fr1.assign(N - 1, {0,-1});
        /*
        УЧТИ?
        fr0
        * * *...
        fr1
        0 * * ...
        здесь первая не учитывается и это надо учесть: как?

        вот как:
        fr0
        левый нижний отрезок (0,1)
        fr1
        левый ниждний отрезок (1,2)
        просто это надо учитывать и все
        */
        //fr0
        for (int i = 0; i + 1 < n; i += 2){
            int mn = a[i], id = i;
            if (a[i] > a[i+1]){
                mn = a[i+1];
                id++;
            }
            fr0[i/2 + N/2 - 1] = {mn, id};
        }

        for (int i = 1; i + 1 < n; i += 2){
            int mn = a[i], id = i;
            if (a[i] > a[i + 1]){
                mn = a[i + 1];
                id++;
            }
            fr1[i/2 + N/2 - 1] = {mn, id};
        }

        for (int i = N/2 - 2; i >= 0; --i){

            /*fr0[i] = max(fr0[i*2 + 1], fr0[i * 2 + 2]);
            fr1[i] = max(fr1[i*2 + 1], fr1[i * 2 + 2]);*/
            pii p = fr0[i*2 + 1];
            if (fr0[i*2 + 2].first > fr0[i*2 + 1].first){
                p = fr0[i*2 + 2];
            }
            fr0[i] = p;
        }

        for (int i = N/2 - 2; i >= 0; --i){
            pii p = fr1[i*2 + 1];
            if (fr1[i*2 + 2].first > fr1[i*2 + 1].first){
                p = fr1[i*2 + 2];
            }
            fr1[i] = p;
        }


        if (sh){
            cout<<"SHOW\n";
            cout<<"MN\n";
            int id=-1;
            for (int lg = 0; lg <= log2(N); ++lg){
                for (int i = 0; i < pow(2, lg); ++i){
                    id++;
                    seep(MN[id]);
                }cout<<"\n";
            }
        }
    }


    void upd(int id){
        id += N - 1;
        MN[id].first = inf;
        while (id > 0){
            id--;
            id /= 2;
            pii p = MN[2 * id + 1];
            if (MN[2 * id + 1].first > MN[2 * id + 2].first){
                p = MN[2 * id + 2];
            }
            MN[id] = p;
        }
    }
};

void slv(){
    tree T;
    T.bld();
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1; if (!sh) cin>>t;
    for (int go = 0; go < t; ++go){
        cin>>n>>k; a.resize(n); for (int &i: a) cin>>i;
        slv();
    }
}
/*
20 20
1 4 3 6 3
1 4 7 4 7
1 4 3 6 4
1 4 3 2 3
*/