#849 small-big-sequence

作問者: wanthor1234

문제

$1$ 부터 $N$ 까지의 정수가 한 번씩만 등장하는 길이 $N$ 의 순열이 있다.

당신은 마지막 수를 제외한 각 원소가 S 또는 B로 가려진 수열을 복원해야 한다.

순열의 $i$ 번째 원소를 $a_i$ 라 할 때, 와 의 정의는 다음과 같다.

i

S

B

S인 경우

$a_i$ 의 오른쪽에 있는 원소들 중, $a_i$ 보다 작은 수의 개수가 $a_i$ 보다 큰 수의 개수보다 작거나 같다.

즉,

|\{j \mid i < j,\ a_j < a_i\}| \le |\{j \mid i < j,\ a_j > a_i\}|

B인 경우

$a_i$ 의 오른쪽에 있는 원소들 중, $a_i$ 보다 작은 수의 개수가 $a_i$ 보다 큰 수의 개수보다 많다.

즉,

|\{j \mid i < j,\ a_j < a_i\}| > |\{j \mid i < j,\ a_j > a_i\}|

주어진 조건을 모두 만족하는 수열 중, 사전순으로 가장 앞서는 것을 복원하시오.

첫 번째 줄에 수열의 길이 $N$ 이 주어진다. $(2 \le N \le 5\,000)$

두 번째 줄에 마지막 수를 제외한 수들이 가려진 수열이 주어진다.

각 원소는 공백으로 구분되어 주어진다.

단, 입력에서 주어지는 수열은 반드시 복원 가능함이 보장된다.

첫 번째 줄에 복원한 순열 중 사전순으로 가장 앞서는 것을 공백으로 구분하여 출력한다.

#	得点	制約
1	100	-

入力例

6
B S B B S 2

出力例

4 3 5 6 1 2

[0]