void _insertionsort(vector<int> &a, int l, int r) {
    for (int i = l + 1; i < r; i++) {
        int j = i;
        while (j > l && a[j - 1] > a[j]) {
            swap(a[j - 1], a[j]);
            j--;
        }
    }
}
void insertionsort(vector<int> &a) {
    _insertionsort(a, 0, a.size());
}