12108. Центри


Відправити розв'язок

Бали: 100
Time limit: 2.0s
Memory limit: 500M

Authors:
Problem type
Allowed languages
C++, Java, Pascal, Python

Вам надано послідовність \(A=(A_1 ,A_2 ,…,A_{3N} )\) довжини \(3N\), де кожне з \(1, 2,… , N\) зустрічається рівно три рази.

Для \(i=1,2,…,N\) нехай \(f(i)\) буде індексом середнього входження \(i\) в \(A\). Відсортуйте \(1,2,…,N\) у порядку зростання \(f(i)\).

Формально \(f(i)\) визначається наступним чином.

  • Припустимо, що такі \(j\), що \(A_j ​ =i\), є \(j=α,β,γ\) \((α<β<γ)\). Тоді \(f(i)=β\).

Обмеження

  • \(1≤N≤10^5\)
  • \(1≤A_j ​ ≤N\)
  • \(i\) зустрічається в \(A\) рівно тричі, для кожного \(i=1,2,…,N\).
  • Усі вхідні значення є цілими числами.

Формат вхідних даних

Перший рядок містить ціле число \(N\).

Наступний   рядок містить цілі числа \(A_i\).

Формат вихідних даних

У вихідний потік виведіть послідовність довжиною \(N\), отриману шляхом сортування \(1,2,…,N\) у порядку зростання \(f(i)\), розділених пробілами.

Приклад вхідних даних

3
1 1 3 2 3 2 2 3 1

Приклад вихідних даних

1 3 2
  • 1 зустрічається в \(A\) в \(A_1 ​, A_2 ​ , A_9\) ​ , тому \(f(1)=2\).
  • 2 зустрічається в \(A\) в \(A_4 ​ , A_6 ​ , A_7 ​\) , тому \(f(2)=6\).
  • 3 зустрічається в \(A\) в \(A_3 ​, A_5 ​ , A_ 8 ​\) , тому \(f(3)=5\).

Таким чином, \(f(1)<f(3)<f(2)\), тому 1,3 і 2 слід вивести в такому порядку.

Приклад вхідних даних

1
1 1 1

Приклад вихідних даних

1

Приклад вхідних даних

4
2 3 4 3 4 1 3 1 1 4 2 2

Приклад вихідних даних

3 4 1 2

Коментарі

Ще немає коментарів.