CF D 2

#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 show(){
        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 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){
            show();
        }
    }


    void upd(int id){
        //!!!
        a[id] = inf;

        //if id % 2 == 0
        int id0, id1;
        id0 = id / 2;
        id1 = (id - 1) / 2;
        int to0, to1; //соседи по паре в fro и fr1
        bool upd0=1, upd1=1;
        if (id == 0){
            upd1 = 0;
        }
        else if (n % 2 == 0 && id == n - 1){
            upd1 = 0;
        }

        if (n % 2 == 1 && id == n - 1){
            upd0 = 0;
        }

        if (id % 2 == 0){
            to0 = id+1;
            to1 = id-1;
        }
        else if (id % 2 == 1){
            to0 = id-1;
            to1 = id+1;
        }

        //fr0
        if (upd0){
            fr0[id0] = {a[id], id};
            if (a[to0] < a[id]){
                fr0[id0] = {a[to0], to0};
            }
        }

        while (upd0 && id0 > 0){
            id0--;
            id0 /= 2;
            pii p = fr0[id * 2 + 1];
            if (fr0[id * 2 + 2].first > fr0[id * 2 + 1].first){
                p = fr0[id * 2 + 2];
            }
            fr0[id] = p;
        }

        //fr1


        //MN
        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();
    /*if (sh){
        int q; cin>>q;
        for (int i = 0; i < q; ++i){
            int id; cin>>id;
            T.upd(id);
            T.show();
        }
    }*/
}


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
*/