Node Merge(Node l, Node r) {
    Node ans;
    if (l.isEmpty) {
        return r;
    }
    if (r.isEmpty) {
        return l;
    }
    ans.len = l.len + r.len;
    ans.lval = l.lval;
    ans.rval = r.rval;
    ans.mid = 0;
    ans.isEmpty = 0;
    ans.isNeub = 0;
    if (r.lval >= l.rval) { // стыковка
        if (l.isNeub) {
            if (r.isNeub) {
                ans.isNeub = 1;
                return ans;
            }
            else {
                ans.L = l.len + r.L;
                ans.mid = r.mid;
                ans.R = r.R;
                return ans;
            }
        }
        if (r.isNeub) {
            if (l.isNeub) {
                ans.L = 0;
                ans.R = 0;
                ans.isNeub = 1;
                return ans;
            }
            else {
                ans.R = l.R + r.len;
                ans.mid = l.mid;
                ans.L = l.L;
                return ans;
            }
        }
        ans.L = l.L;
        ans.R = r.R;
        ans.mid = ((l.R + r.L) * (l.R + r.L + 1)) / 2 + l.mid + r.mid;
        return ans;
    }
    else { // нестыковка
        if (l.isNeub) {
            if (r.isNeub) {
                ans.L = l.len;
                ans.R = r.len;
                ans.mid = 0;
                return ans;
            }
            else {
                ans.L = l.len;
                ans.mid = ((r.L) * (r.L + 1)) / 2 + r.mid;
                ans.R = r.R;
                return ans;
            }
        }
        if (r.isNeub) {
            if (l.isNeub) {
                ans.L = l.len;
                ans.R = r.len;
                ans.mid = 0;
                return ans;
            }
            else {
                ans.L = l.L;
                ans.mid = (l.R * (l.R + 1)) / 2 + l.mid;
                ans.R = r.len;
                return ans;
            }
        }
        ans.L = l.L;
        ans.R = r.R;
        ans.mid = (l.R * (l.R + 1)) / 2 + ((r.L) * (r.L + 1)) / 2 + l.mid + r.mid;
        return ans;
    }
}