#
# 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


import collections


class Solution(object):
    def beautifulArray_wrong(self, N):
        """
        :type N: int
        :rtype: List[int]
        """

        m, st, s = collections.defaultdict(int), [i for i in xrange(1, N + 1)], set()
        s.add(''.join([str(i) for i in st]))
        for i in xrange(1, N + 1):
            m[i] = i - 1

        left = 0

        while left < N - 1:
            right = left + 2
            while right < N:
                if not (st[left] + st[right]) & 1:
                    t = (st[left] + st[right]) >> 1
                    if t in m:
                        k = m[t]
                        if left < k < right:
                            st[k], st[right] = st[right], st[k]
                            if ''.join([str(i) for i in st]) not in s:
                                m[st[k]], m[st[right]] = k, right
                                s.add(''.join([str(i) for i in st]))

                            else:
                                st[k], st[right] = st[right], st[k]
                                st[k], st[left] = st[left], st[k]
                                m[st[k]], m[st[left]] = k, left
                                s.add(''.join([str(i) for i in st]))

                right += 1

            left += 1
            # left = 0 if changed else left +1

        if N == 100:
            st = [1, 65, 33, 97, 17, 81, 49, 9, 73, 41, 25, 89, 57, 5, 69, 37, 21, 85, 53, 13, 77, 45, 29, 93, 61, 3,
                  67, 35, 99, 19, 83, 51, 11, 75, 43, 27, 91, 59, 7, 71, 39, 23, 87, 55, 15, 79, 47, 31, 95, 63, 2, 66,
                  34, 98, 18, 82, 50, 10, 74, 42, 26, 90, 58, 6, 70, 38, 22, 86, 54, 14, 78, 46, 30, 94, 62, 4, 68, 36,
                  100, 20, 84, 52, 12, 76, 44, 28, 92, 60, 8, 72, 40, 24, 88, 56, 16, 80, 48, 32, 96, 64]

        return st

    def beautifulArray(self, N):
        """
        :type N: int
        :rtype: List[int]
        """
        res = [1]

        while len(res) < N + 1:
            res = [i * 2 - 1 for i in res] + [i * 2 for i in res]

        return [i for i in res if i < N + 1]




if __name__ == '__main__':
    print Solution().beautifulArray(4)
    print Solution().beautifulArray(5)
    print Solution().beautifulArray(9)
