#include <stdio.h>

// 主函数：原地重排数组
void reorderArray(int arr[], int n) {
    if (n <= 2) return;
    
    // 将数组分成两半：[1,2,3] 和 [4,5,6]
    // 目标：合并成 [1,4,2,5,3,6]
    
    int mid = n / 2;
    
    // 将后半部分插入到前半部分的间隙中
    for (int i = 1; i < n; i += 2) {
        // 每次从后半部分取一个元素
        int element = arr[mid + i/2];
        
        // 将i位置之后的元素后移一位
        for (int j = mid + i/2; j > i; j--) {
            arr[j] = arr[j - 1];
        }
        
        // 插入元素
        arr[i] = element;
        
        // 更新mid（因为数组长度没变，但后半部分的起始位置变了）
        mid++;
    }
}