치팅 방지

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

요약

같은 반 학생끼리의 최소 거리가 최대가 되도록 한 줄의 좌석에 반 번호를 배치하고, 그 수열을 출력합니다.

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

문제

한과영 학생들이 정보과학2 시험을 치기 위해 일렬로 앉아 있다. 각 학생은 1반부터 N반 중 한 반에 소속되어 있다. 같은 반 학생끼리 너무 가까이 앉으면 치팅을 할 수 있다.

양의 정수 $K_1, K_2, \cdots, K_N$ 이 주어진다. $K_i$ 는 $i$ 반에 속한 학생의 수이다. 학생들을 잘 정렬하여 같은 반에 속한 임의의 두 학생 사이 거리의 최솟값을 최대화하려고 한다. 조건을 만족하는 정렬 방법을 찾아라. 정확히는, 왼쪽에서 $i$ 번째로 앉는 학생의 반 번호를 $i$ 번째 원소로 하는 수열 $X$ 를 찾아라.

예를 들어 $N=3$ 이고 $K_1=1, K_2=2, K_3=3$ 인 경우를 보자. 이는 1반 학생이 1명, 2반 학생이 2명, 3반 학생이 3명 있다는 뜻이다.

이 경우 $X=[3, 2, 3, 1, 3, 2]$ 은 하나의 답이 될 수 있다. $X_i = X_j$ 를 만족하는 두 정수 $i$ , $j$ 에 대해 $|i-j|$ 의 최솟값이 2이므로, 같은 반 학생 사이 거리의 최솟값은 2이다. 이 값이 2보다 큰 정렬 방법은 존재하지 않는다는 것을 증명할 수 있다.

입력

첫 번째 줄에 정수 $N$ 이 주어진다.

두 번째 줄에 $N$ 개의 정수 $K_1, K_2, \cdots, K_N$ 이 주어진다.

출력

조건을 만족하는 수열 $X$ 의 정수 $\mathrm{sum}(K)$ 개 $X_1, X_2, \cdots, X_{\mathrm{sum}(K)}$ 을 출력한다.

답이 여러 개 존재한다면 아무거나 출력해도 상관없다.

제한

$1 \leq N \leq 10^5$
$1 \leq \mathrm{sum}(K) \leq 10^{5}$

예제2

예제 1
입력
```
3
2 2 2
```
예상 출력
```
1 2 3 1 2 3
```
예제 2
입력
```
3
1 2 3
```
예상 출력
```
3 2 3 1 3 2
```