//#define pragma

#ifdef pragma
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif // pragma

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define all(x) begin(x), end(x)
#define pb push_back
#define x first
#define y second
//#define int long long
#define zero(two) memset(two, 0, sizeof(two))

using namespace std;
using namespace __gnu_pbds;


typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef long double ld;
typedef vector<vi> matrix;
template<typename T>
using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ld PI = atan2(0, -1);

void seriy() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    cout << fixed << setprecision(10);
    #if _offline
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        freopen("next.in", "r", stdin);
        freopen("next.out", "w", stdout);
    #endif
}

const int MAXN = 2e5 + 10;
const int INF = 2e9 + 7;
const int MAXLOG = 20;
const int MOD = 1e9;
const int BASE = 47;
const int MAX = (1ll << 32) - 1;

struct treap {
    int x, y, sz = 1, num;
    treap *left = nullptr;
    treap *right = nullptr;

    treap(int x1, int y1, int num1) {
        x = x1;
        y = y1;
        num = num1;
    }
};

treap *root;
vi parent;
vector<treap*> nodes;
mt19937 rr(47);

void add(treap *cur, treap *v) {
    if(cur->y < v->y) {
        if(cur->right != nullptr) {
            v->left = cur->right;
            parent[v->left->num] = v->num;
        }
        cur->right = v;
        parent[v->num] = cur->num;
        return;
    }
    else {
        if(parent[cur->num] == -1) {
            v->left = cur;
            parent[cur->num] = v->num;
            return;
        }
        else {
            add(nodes[parent[cur->num]], v);
        }
    }
}

void update(treap *a) {
    int sz1 = ((a->left == nullptr) ? 0 : a->left->sz);
    int sz2 = ((a->right == nullptr) ? 0 : a->right->sz);
    a->sz = sz1 + sz2 + 1;
}

treap *unite(treap *a, treap *b) {
    if(a == nullptr) return b;
    if(b == nullptr) return a;
    if(a->y > b->y) {
        a->right = unite(a->right, b);
        update(a);
        return a;
    }
    else {
        b->left = unite(a, b->left);
        update(b);
        return b;
    }
}

pair<treap*, treap*> split(treap *a, int k) {
    if(a == nullptr) return {nullptr, nullptr};
    int l = ((a->left == nullptr) ? -1 : a->left->sz);
    if(k <= l) {
        pair<treap*, treap*> kek = split(a->left, k);
        a->left = kek.y;
        update(a);
        return {kek.x, a};
    }
    else {
        pair<treap*, treap*> kek = split(a->right, k - l - 1);
        a->right = kek.x;
        update(a);
        return {a, kek.y};
    }
}

treap *get_parent(treap *a) {
    if(parent[a->num] == -1) {
        return a;
    }
    else {
        return get_parent(nodes[parent[a->num]]);
    }
}

void build(int n) {
    parent.resize(n, -1);
    root = new treap(1, rr(), 0);
    nodes.pb(root);
    for(int i = 2; i <= n; i++) {
        nodes.pb(new treap(i, rr(), i - 1));
    }
    treap *now = nodes[0];
    for(int i = 1; i < n; i++) {
        add(now, nodes[i]);
        now = nodes[i];
    }
    root = get_parent(root);
}

void change(int l, int r) {
    pair<treap*, treap*> kek = split(root, l);
    pair<treap*, treap*> lol = split(kek.y, r - l + 1);
    lol.x = unite(lol.x, kek.x);
    root = unite(kek.x, lol.y);
}

void print(treap *a) {
//    cerr << 1 << '\n';
    if(a == nullptr) return;
    print(a->left);
    cout << a->x << " ";
    print(a->right);
}

signed main() {
    seriy();
    int n, m;
    cin >> n >> m;
    build(n);
    while(m--) {
        int l, r;
        cin >> l >> r;
//        change(l, r);
    }
    pair<treap*, treap*> kek = split(root, 3);
    print(kek.y);
//    print(root);
    return 0;
}