<p>An array <code>nums</code> of length <code>n</code> is <strong>beautiful</strong> if:</p>

<ul>
	<li><code>nums</code> is a permutation of the integers in the range <code>[1, n]</code>.</li>
	<li>For every <code>0 &lt;= i &lt; j &lt; n</code>, there is no index <code>k</code> with <code>i &lt; k &lt; j</code> where <code>2 * nums[k] == nums[i] + nums[j]</code>.</li>
</ul>

<p>Given the integer <code>n</code>, return <em>any <strong>beautiful</strong> array </em><code>nums</code><em> of length </em><code>n</code>. There will be at least one valid answer for the given <code>n</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> n = 4
<strong>Output:</strong> [2,1,4,3]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> n = 5
<strong>Output:</strong> [3,1,2,5,4]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
</ul>

class Solution {
public:
    unordered_map<int, vector<int>> mp; // from 1~N, valid permutation

    //for example, N=5
    //there are 2 even and 3 odd nums
    // permutation range for 2 is from 1~2 and the sequence is valid ---C1
    // permutation range for 3 is from 1~3 and the sequence is valid ---C2
    // permutation range for 5 is taking 1~3 from 3 and 1~2 from 2
    // we get all 3 odd from 1~5 by using 3*x-1 and get all 2 even by usinf 2*x ---C3 
    // [1~3 permutation] [1~2 permutation]
    // since 2*b=a+c, 2*b is always even, so if put all odd in left all even in right, there's no way to satisfy the condition 2*b=a+c, the way to get all odd and even from 1~N is described as above

    vector<int> split(int N){
        
        if(mp.count(N)) return mp[N];

        vector<int> arr;
        if(N==1){
            arr.push_back(1);
        }
        else{
            for(auto odd: split((N+1)/2)){
                arr.push_back(2*odd-1);
            }
            for(auto even: split((N)/2)){
                arr.push_back(2*even);
            }
        }
        
        return mp[N]=arr;
    }

    vector<int> beautifulArray(int n) {

        return split(n);

    }
};
11000