Naive Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int reinitializePermutation(int n) {\n        int count = 0;\n        vector<int> perm;\n        for(int i = 0; i < n; i++){\n            perm.push_back(i);\n        }\n        vector<int> arr;\n        do{\n        for(int i = 0; i < n; i++){\n            if(i % 2 == 0){\n                arr.push_back(perm[i/2]);\n            }\n            else{\n                arr.push_back(perm[n/2 + (i-1) / 2]);\n            }\n        }\n        count++;\n        perm.clear();\n        copy(arr.begin(), arr.end(), back_inserter(perm));\n        arr.clear();\n        \n        }\n        while(!is_sorted(perm.begin(), perm.end()));\n        return count;\n    }\n};\n```
['Array', 'Math', 'Simulation', 'C++']