stable_partition

Lab C++ Intermediate 20 points

Read n integers and move all even numbers before the odd ones while keeping their relative order, with stable_partition.

Input

Line 1: n. Line 2: n integers.

Output

One line.

Example

Input

8
1 2 3 4 5 6 7 8

Output

2 4 6 8 1 3 5 7

Sample input available Sample output available

Editor

C++

Hints

stable_ versions keep equal elements in their original order.

Solution explanation

partition is faster but may reorder; stable_partition preserves order.

Show solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int &x : v) cin >> x;
    stable_partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
    for (int i = 0; i < n; i++) cout << v[i] << (i < n - 1 ? " " : "\n");
    return 0;
}

Output

Answer