class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        N = len(nums)
        even_idx = 0
        odd_idx = 1
        while True:
            while even_idx < N and nums[even_idx] % 2 == 0:
                even_idx += 2
            while odd_idx < N and nums[odd_idx] % 2 == 1:
                odd_idx += 2
            if even_idx >= N:
                break
            nums[even_idx], nums[odd_idx] = nums[odd_idx], nums[even_idx]
        return nums