def segregateEvenOdd(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        while (arr[left] % 2 == 0 and left < right):
            left += 1
        while (arr[right] % 2 == 1 and left < right):
            right -= 1
        print(left,right)
        if (left < right):
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right = right - 1
            print(arr)

#Method 2 - Lomuto partition
def rearrangeEvenAndOdd(arr, n):
    j = -1
    for i in range(0, n):
        if (arr[i] % 2 == 0):
            j = j + 1
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp


arr = [12, 34, 45, 9, 8, 90, 3]
segregateEvenOdd(arr)