You are given an even integer n​​​​​​. You initially have a permutation perm of size n​​ where perm[i] == i​ (0-indexed)​​​​.

In one operation, you will create a new array arr, and for each i:


	If i % 2 == 0, then arr[i] = perm[i / 2].
	If i % 2 == 1, then arr[i] = perm[n / 2 + (i - 1) / 2].


You will then assign arr​​​​ to perm.

Return the minimum non-zero number of operations you need to perform on perm to return the permutation to its initial value.

&nbsp;
Example 1:

Input: n = 2
Output: 1
Explanation: perm = [0,1] initially.
After the 1st operation, perm = [0,1]
So it takes only 1 operation.


Example 2:

Input: n = 4
Output: 2
Explanation: perm = [0,1,2,3] initially.
After the 1st operation, perm = [0,2,1,3]
After the 2nd operation, perm = [0,1,2,3]
So it takes only 2 operations.


Example 3:

Input: n = 6
Output: 4


&nbsp;
Constraints:


	2 &lt;= n &lt;= 1000
	n​​​​​​ is even.


class Solution:
    def reinitializePermutation(self, n: int) -> int:
        ans = 0
        perm = list(range(n))
        while True: 
            ans += 1
            perm = [perm[n//2+(i-1)//2] if i&1 else perm[i//2] for i in range(n)]
            if all(perm[i] == i for i in range(n)): return ans
class Solution {
    public int reinitializePermutation(int n) {
        int ans = 1;
        int num = 2;
        if(n == 2) return 1;
        while(true){
            if(num % (n-1) == 1)break; 
            else {
                ans++;
                num = (num * 2) % (n-1);
            }
        }
        return ans;
        
    }
}
class Solution {
public:
    vector<int> change(vector<int>arr,vector<int>v){
        int n=v.size();
         for(int i=0;i<n;i++){
            if(i%2==0){
                arr[i]=v[i/2];
            }
            else{
                arr[i]=v[(n/2) + ((i-1)/2) ];
            }
        }
        return arr;
    }
    int reinitializePermutation(int n) {
        vector<int>v(n);
        for(int i=0;i<n;i++){
            v[i]=i;
        }
        vector<int>arr(n);

        arr=change(arr,v);
        if(arr==v){return 1;}

        int cnt=1;

        while(arr!=v){
            arr=change(arr,arr);
            cnt++;
            if(arr==v){return cnt;}

        }
        return cnt;
    }
};
 * @param {number} n
 * @return {number}
 */
var reinitializePermutation = function(n) {
  if (n < 2) return 0;
  let prem = [];
  let count = 0;
  for (var i = 0; i < n; i++) {
    prem[i] = i;
  }
  let newArr = [];
  newArr = helper(prem, newArr);

  const equals = (a, b) => JSON.stringify(a) === JSON.stringify(b);

  if (equals(prem, newArr)) {
    count++;
    return count;
  } else {
    while (!equals(prem, newArr)) {
      count++;
      let temp = newArr;
      newArr = [];
      newArr = helper(temp, newArr);
    }
  }
  return count + 1;
};

var helper = function (prem, arr) {
  let n = prem.length;
  for (var i = 0; i < n; i++) {
    if (i % 2 == 0) {
      arr[i] = prem[i / 2];
    } else {
      arr[i] = prem[n / 2 + (i - 1) / 2];
    }
  }
  return arr;
};
Minimum Number of Operations to Reinitialize a Permutation