You are given an even integer n. Initially, you have a permutation perm of size n where perm[i] is equal to i for each 0 \le i < n ($0$ indexed).

In each step, you create a new array arr of size n defined as follows:

• If i % 2 == 0, then arr[i] = perm[i / 2]

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

You then assign arr to perm.

Return the minimum non-zero number of operations required to return the permutation perm back to its initial configuration.

Constraints:

• $2 \le$ n $\le 1000$

• n is even.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.