class Solution(object):
    def sortArrayByParityII(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        odds, evens, res = [], [], []
        for n in A:
            if n & 1:
                odds.append(n)
            else:
                evens.append(n)
        l, m = 0, 0
        while l < len(odds) and m < len(evens):
            res.append(evens[m])
            res.append(odds[l])
            m, l = m + 1, l + 1

        return res


if __name__ == '__main__':
    print Solution().sortArrayByParityII([4, 2, 5, 7])
