읽기 쉬운 단어

마르스 알파벳은 1부터 $10^9$까지의 정수 $10^9$개로 이루어져 있다. 홀수는 모음, 짝수는 자음이다. 단어는 이런 정수들의 수열이다.

단어에서 정수의 순서를 바꿔도 뜻은 달라지지 않지만, 발음은 달라진다. 단어에서 인접한 두 정수가 항상 모음 하나와 자음 하나로 이루어져 있으면, 그 단어를 읽기 쉬운 단어라고 부른다.

Vasya Pupkin은 화성에서 지구 요리 식당을 열려고 한다. 식당 이름을 만들려고 나무 정수 $n$개를 샀고, 이를 1번부터 $n$번까지 번호가 붙은 받침대 $n$개 위에 한 줄로 놓았다. 받침대 $i$에 놓인 정수를 $a_i$라고 한다.

정수를 받침대 $i$에서 받침대 $j$로 옮기는 데 $|i - j|$ 마르스 루블이 든다. 재배열하는 동안에는 한 받침대에 정수가 둘 이상 놓여도 되지만, 마지막에는 모든 받침대에 정수가 정확히 하나씩 놓여야 한다.

정수를 재배열해서 만든 읽기 쉬운 단어 중 비용이 가장 적은 것을 찾아라. 그런 단어가 여러 개라면 사전순으로 가장 앞선 것을 골라라.

같은 길이의 수열 $b$가 수열 $c$보다 사전순으로 작다는 것은, 어떤 $j$가 존재해서 모든 $i < j$에 대해 $b_i = c_i$이고 $b_j < c_j$인 것을 뜻한다.

첫째 줄에 단어를 이루는 마르스 문자의 개수 $n$이 주어진다 ($1 \leq n \leq 10^5$).

둘째 줄에 문자 자체인 정수 $a_i$가 공백으로 구분되어 $n$개 주어진다 ($1 \leq a_i \leq 10^9$).

해가 존재함이 보장된다.

요구하는 읽기 쉬운 단어를 공백으로 구분된 정수 $n$개로 한 줄에 출력한다.