카드 뒤집기 1

면접 대비

시간 제한2초메모리 제한1024 MB

요약

N장의 카드 앞면에 p_1부터 p_N까지 정수가 적혀 있습니다. 앞 카드의 위 수가 뒤 카드보다 크면 뒤 카드를 뒤집는 규칙을 적용한 뒤 각 카드 위의 수를 구합니다.

난이도: 보통10점 중 6점
유형: 세그먼트 트리, 수학
정답자: 아직 제출이 없습니다

문제

카드 뒤집기 1과 2는 서로 다른 문제다.

준원이는 카드 $N$ 장을 가지고 있다. 카드의 앞면에는 정수 $1,2,\cdots ,N$ 이 하나씩 적혀 있고, 뒷면에는 모두 정수 $0$ 이 적혀 있다. 준원이는 카드의 순서를 마음대로 바꾼 뒤 $N$ 장의 카드를 윗면이 천장을 향하도록 나열했다. 이때 천장을 향하는 면에 적힌 정수를 $p_1,p_2,\cdots ,p_N$ 이라고 하자.

준원이는 $i$ 를 $1$ 부터 $N$ 까지 $1$ 씩 키우면서 다음 행동을 반복한다.

$i$ 번째 카드와 $j$ ( $i<j\le N$ )번째 카드를 비교한다. 두 카드의 천장을 향하는 면에 적힌 정수를 각각 $X,Y$ 라고 할 때, $X>Y$ 를 만족하는 모든 $j$ 번째 카드를 뒤집는다.

모든 행동을 마친 뒤, 각 카드의 천장을 향하는 면에 적힌 정수를 구한다.

입력

첫째 줄에 정수 $N(1\le N\le 200\,000)$ 이 주어진다.

둘째 줄에 정수 $p_1,p_2,\cdots ,p_N(1\le p_i\le N)$ 이 공백으로 구분되어 주어진다.

출력

모든 행동을 마친 뒤, 각 카드의 천장을 향하는 면에 적힌 정수를 공백으로 구분하여 출력한다.

예제3

예제 1
입력
```
4
1 2 3 4
```
예상 출력
```
1 2 3 4
```
예제 2
입력
```
4
3 4 2 1
```
예상 출력
```
3 4 2 0
```
예제 3
입력
```
5
3 2 5 4 1
```
예상 출력
```
3 0 5 0 1
```