DOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord-backed certification.

Problems

Community

Account

Policy

#842 선행 관계

Problem #842

선행 관계

projects

[0]

Authors: abcdana

문제

창업동아리 모나드는 $N$ 개의 연구개발(R&D) 프로젝트를 계획하고 있다. 프로젝트 $i$ 의 난이도는 $A_i$ 로 나타내며, $A_i$ 가 클수록 프로젝트 는 어렵다.

You must log in to submit.

[0]

i

다음 조건을 모두 만족하면 프로젝트 $i$ 는 프로젝트 $j$ 의 선행 프로젝트이다.

$1 \le i < j \le N$
프로젝트 $j$ 는 프로젝트 $i$ 보다 어렵다. 즉, $A_j > A_i$ 이다.
$i \le k < j$ 인 임의의 $k$ 에 대하여 프로젝트 $k$ 는 프로젝트 $i$ 보다 어렵지 않다. 즉, $(\max_{i \leq k <}$ 이다.

위 조건을 하나라도 만족하지 않는다면 프로젝트 $i$ 는 프로젝트 $j$ 의 선행 프로젝트가 아니다.

모나드의 창업동아리장은 프로젝트 계획을 효율적으로 관리하기 위해 각 프로젝트의 실행 단계를 정하기로 하였다. 프로젝트 $i$ 의 실행 단계는 $t_i$ 이다.

각 프로젝트의 실행 단계는 다음을 만족하여야 한다.

t_i = \begin{cases} 1 & \text{프로젝트 }i\text{의 선행 프로젝트가 없는 경우}\\ 1+\displaystyle\max_{j\rightarrow i}t_j & \text{프로젝트 }i\text{의 선행 프로젝트가 있는 경우} \end{cases}

여기서 $j\rightarrow i$ 는 프로젝트 $j$ 가 프로젝트 $i$ 의 선행 프로젝트임을 의미한다.

모나드의 창업동아리장을 도와 각 프로젝트의 실행 단계를 정해 주자.

첫 번째 줄에 프로젝트의 수 $N$ 이 주어진다. $(1 \le N \le 10^6)$

두 번째 줄에 각 프로젝트의 난이도를 나타내는 정수 $A_1, A_2, \dots, A_N$ 이 공백으로 구분되어 주어진다. $(1 \le A_i \le N)$

모든 $A_i$ 는 서로 다르다.

첫 번째 줄에 $t_1, t_2, \dots, t_N$ 을 공백으로 구분하여 출력한다.

만약 조건을 만족하는 수열 $t$ 가 여러 가지라면 그중 아무거나 출력한다.

단, 조건을 만족하는 수열 $t$ 가 존재하지 않는다면 $\texttt{-1}$ 을 출력한다.

#	Score	Constraints
1	100	-

Input

5
3 1 2 5 4

Output

1 1 2 3 1

j

A_{k}

\leq

A_{i}

)

\left(\displaystyle\max_{i \le k<j} A_k \le A_i\right)

(i \leq k < j max A_{k} \leq A_{i})