Problem Description

Sort an array where even numbers are sorted in ascending order and odd numbers are sorted in descending order, while maintaining their relative positions to each other.

Input Format

First line contains n (array size). Second line contains n space-separated integers.

Output Format

Array with even numbers sorted ascending and odd numbers sorted descending, space-separated.

Constraints

• 1 ≤ n ≤ 1000

• -1000 ≤ array elements ≤ 1000

• Maintain relative positions between even and odd groups

• Even numbers: ascending order

• Odd numbers: descending order

Sample Input/Output

6
4 3 2 7 1 6

2 7 4 3 1 6

Explanation

Original: [4,3,2,7,1,6]. Evens: [4,2,6] → sorted: [2,4,6]. Odds: [3,7,1] → sorted desc: [7,3,1]. Merge maintaining positions: [2,7,4,3,1,6].