void insert_nonfull(btree* &x, int k) {
int i = x->n;
if (x->leaf) {
while (i >= 1 && k<x->arr[i - 1].key) {
x->arr[i].key = x->arr[i - 1].key;
i = i - 1;
}
x->arr[i].key = k;
x->n = x->n + 1;
}
else {
while (i >= 1 && k<x->arr[i - 1].key)
i = i - 1;
i = i + 1;
if (x->arr[i - 1].child->n == (2 * t - 1)) {
split_child(x, i - 1);
if (k>x->arr[i - 1].key)
i = i + 1;
}
insert_nonfull(x->arr[i - 1].child, k);
}
}

void insert(btree* &root, int k) {
btree* r = new btree;
r = root;
if (r->n == (2 * t - 1)) {

btree* s = new btree;
s->arr = new node[2 * t];
s->leaf = false;
s->n = 0;
s->arr[0].child = r;

root = s;
split_child(s, 0);
insert_nonfull(s, k);
}
else
insert_nonfull(r, k);
}