화학 실험

면접 대비

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

요약

합이 N인 K개 색의 개수가 주어질 때, 이웃한 두 시험관의 색이 다르도록 N개를 나열하고, 불가능하면 -1을 출력한다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 힙, 구현
정답자: 아직 제출이 없습니다

문제

화학 실험을 하던 윤이는 일렬로 나열한 $N$ 개의 시험관에서 재미있는 특징을 발견했다. 이웃한 시험관 쌍마다 두 시험관에 든 시약의 색깔이 서로 다르다는 점이었다. 흥미롭다고 느낀 윤이는 실험보고서에 이 사실과 함께 색깔별 시약의 수를 적었다. 하지만 보고서를 채점하던 조교 원이는 윤이가 색깔별 시약의 수를 제대로 적었는지 의문이 들었다. 윤이의 보고서와 일치하도록 시험관을 배열할 수 있는지 판별하는 프로그램을 작성하시오.

입력

첫 번째 줄에 시험관의 개수 $N$ 과 색깔의 종류 수 $K$ 가 공백을 사이에 두고 주어진다.

두 번째 줄에 $K$ 개의 양의 정수 $c\_i$ 가 공백을 사이에 두고 주어진다. 각 색깔에는 번호가 붙어 있으며, $c\_i$ 는 $i$ 번 색깔의 시약이 담긴 시험관의 개수이다. $(1≤i≤K)$

출력

조건을 만족하는 시험관 배열을 만들 수 있으면, 시험관의 색깔 번호를 공백으로 구분하여 순서대로 출력한다. 답이 여러 개이면 아무 거나 출력한다.

조건을 만족하는 시험관 배열을 만들 수 없으면 $-1$ 을 출력한다.

제한

$1 ≤ K ≤ N ≤ 300,000$

$c\_1, \cdots, c\_k > 0$

$c\_1+\cdots+c\_k = N$

예제2

예제 1
입력
```
6 3
3 1 2
```
예상 출력
```
1 2 3 1 3 1
```
예제 2
입력
```
6 3
4 1 1
```
예상 출력
```
-1
```