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
Коментарі