using System;
public class Program
{
public static void ArrangeEvenOdd(int[] arr) {
int left = 0;
int right = arr.Length - 1;
while (left < right) {
if ((arr[left] % 2) != 0) { // odd
while ((arr[right] % 2 == 1) && right > left) {
right--;
}
int tmp = arr[left];
arr[left++] = arr[right];
arr[right--] = tmp;
}
else { // even
left++;
}
}
}
public static void Main(string[] args)
{
int[] arr = new int[] {3, 4, 2, 9, 4, 8, 5, 6};
ArrangeEvenOdd(arr);
foreach (int n in arr) {
Console.Write(n + " ");
}
}
}
/*
run:
6 4 2 8 4 9 5 3
*/