Polycarp has an array consisting of n integers.

He wants to play a game with this array. The game consists of several moves. On the first move, he chooses any element and deletes it (after the first move the array contains n−1 elements).

For each of the next moves he chooses any element with the only restriction: its parity should differ from the parity of the element deleted on the previous move. In other words, he alternates parities (even-odd-even-odd-… or odd-even-odd-even-…) of the removed elements. Polycarp stops if he can’t make a move.

Formally:

1. If it is the first move, he chooses any element and deletes it;

2. If it is the second or any next move:

– if the last deleted element was odd, Polycarp chooses any even element and deletes it;

– if the last deleted element was even, Polycarp chooses an odd element and deletes it.

3. If after some move Polycarp cannot make a move, the game ends.

Polycarp’s goal is to minimize the sum of non-deleted elements of the array after the end of the game. If Polycarp can delete the whole array, then the sum of non-deleted elements is zero.

Help Polycarp find this value.

**Input:**
The first line of the input contains one integer n — the number of elements of a.
The second line of the input contains n integers a1,a2,…,an, where ai is the i-th element of a.
**Output:**
Print one integer — the minimum possible sum of non-deleted elements of the array after the end of the game.

#include <stdio.h> #include <stdlib.h> int cmp(const void *a, const void *b){ return *(int*)a - *(int*)b; } int main(){ int o[2000], ol = 0, e[2000], el = 0, n, t; scanf("%d", &n); while(n--) { scanf("%d", &t); if(t % 2) o[ol++] = t; else e[el++] = t; } qsort(o, ol, sizeof(int), cmp); qsort(e, el, sizeof(int), cmp); while(ol && el) { ol--; el--; } t = 0; if(ol) { ol--; while(ol) t += o[--ol]; } else if(el) { el--; while(el) t += e[--el];} printf("%d", t); return 0; }

**INPUT_1:**

5

2 1 1 1 1

**OUTPUT:**

2

**INPUT_2:**

5

1 1 1 1 1

**OUTPUT:**

4

**ILLUSTRATION**

**Morae Q!**

- Find the length of the array’s longest increasing sub-sequence.
- Arrange numbers in a circle so that any two neighbouring numbers differ by 1.
- Find partial names and count the total numbers.
- Find the minimized sum of non-deleted elements of the array after the end of the game.
- Find the maximum number of good sleeping times optimally.
- Sort the elements of the array in the order in which they are required.
- Find the minimum number of flats, monkey needs to visit to catch ninjas.
- Convert the square matrix to matrix in Z form.
- Shift the K elements of each row to right of the matrix.
- Find maximum possible number of students in a balanced team with skills.
- Find the Maximum number of pairs of points you can match with each other.
- Calculate the number of non-empty good subarrays of given array.
- Transform the binary string A into the string B using finite operations.
- Find the number of potion must the character take to jump the hurdles.
- Count the total number of vowels and consonants.
- Return all elements of the matrix in spiral order.
- Return all palindromic paths of the matrix.
- Write the code to change the display in reverse order using pointer.
- Find the number of days the expedition can last.
- Find the minimum size of the sub-segment to make the array pairwise distinct.