#include <bits/stdc++.h>
using namespace std;

#define INF 0x3f3f3f3f

struct Node {
    Node *lc, *rc;
    int val, sz, Max;
    Node (int val) {
        this->val = val;
        sz = 1;
        lc = rc = NULL;
    }
}*root;

int SZ(Node* o) {
    return o == NULL ? 0 : o->sz;
}

int get_max(Node* o) {
    return o == NULL ? -INF : o->Max;
}

void maintain(Node* o) {
    o->sz = 1 + SZ(o->lc) + SZ(o->rc);
    o->Max = max(o->val, max(get_max(o->lc), get_max(o->rc)));
}

void split(Node* o, int k, Node* &left, Node* &right) {
    if (o == NULL) {
        left = right = NULL;
        return;
    }

    if (k <= SZ(o->lc)) {
        right = o;
        split(o->lc, k, left, right->lc);
    } else {
        left = o;
        split(o->rc, k - SZ(o->lc) - 1, left->rc, right);
    }
    maintain(o);
}

Node* merge(Node* left, Node* right) {
    if (left == NULL) return right;
    if (right == NULL) return left;

    static int x;
    if (x++ % (left->sz + right->sz) < left->sz) {
        left->rc = merge(left->rc, right);
        maintain(left);
        return left;
    } else {
        right->lc = merge(left, right->lc);
        maintain(right);
        return right;
    }
}

void print(Node* o) {
    if (o == NULL) return;
    print(o->lc);
    printf("%d ", o->val);
    print(o->rc);
}

int main() {
    root = NULL;
    for (int i = 1; i <= 10; i++) {
        root = merge(root, new Node(i));
    }

    Node *left, *mid, *right, *tmp;
    split(root, 3, left, tmp);
    split(tmp, 4, mid, right);

    print(left); puts("");
    printf("Max = %d\n", left->Max);
    print(mid); puts("");
    printf("Max = %d\n", mid->Max);
    print(right); puts("");
    printf("Max = %d\n", right->Max);

    root = merge(left, merge(mid, right));
    print(root); puts("");

    return 0;
}