Haar

#include <iostream>
#include <vector>
#include <random>
#include <ctime>
using namespace std;

typedef long long ll;

vector<ll> a;

void Haar(ll l, ll r){
    ll i = l, j = r, x = a[(l + r) / 2];
    cout << "l=" << l << " r=" << r << endl;
    if(l >= r){
        return;
    }
    while(i < j){
        while(a[i] < x){
            i++;
        }
        while(a[j] > x){
            j--;
        }
        if(i < j){
            swap(a[i],a[j]);
            cout << i << " " << j << " " << x << " " << endl;
            for(ll i = 0; i < a.size(); i++){
                cout << a[i] << " ";
            }
            cout << endl;
            i++;
            j--;
        }
    }
    Haar(l,j);
    Haar(j+1,r);
}

int main(){
    srand(time(0));
    ll n;
    cin >> n;
    a.resize(n);
    for(ll i = 0; i < n; i++){
        a[i] = rand() % 10000 + 1;
    }
    Haar(0,a.size()-1);
    for(ll i = 0; i < n-1; i++){
        cout << a[i] << " ";
    }
    cout << endl;
    for(ll i = 0; i < n-1; i++){
        if(a[i] > a[i+1]){
            cout << i << endl;
            cout << a[i] << " " << a[i+1] << endl;
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}