For some fixed N, an array A is beautiful if it is a permutation of the integers 1, 2, ..., N, such that:
For every i < j, there is no k with i < k < j such that A[k] * 2 = A[i] + A[j].
Given N, return any beautiful array A.  (It is guaranteed that one exists.)
Example 1:
Input: 4
Output: [2,1,4,3]
Example 2:
Input: 5
Output: [3,1,2,5,4]
Note:
1 <= N <= 1000
class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        answers = []
        
        queue = [list(range(1, N + 1))]
        while queue:
            ls = queue.pop()
            if len(ls) > 2:
                odd = []
                even = []
                
                for i, val in enumerate(ls):
                    if i % 2:
                        odd.append(val)
                    else:
                        even.append(val)
                
                queue.append(odd)
                queue.append(even)
            else:
                answers += ls
        
        return answers
class Solution:
    def beautifulArray(self, N: int) -> List[int]:
        answers = []
        
        queue = [list(range(1, N + 1))]
        while queue:
            ls = queue.pop()
            if len(ls) > 2:
                odd = []
                even = []
                
                for i, val in enumerate(ls):
                    if i % 2:
                        odd.append(val)
                    else:
                        even.append(val)
                
                queue.append(odd)
                queue.append(even)
            else:
                answers += ls
        
        return answers