시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB75583.333%

문제

숲 속 마을에 흰곰, 흑곰, 토끼가 살고 있다. 흰곰은 흑곰에게 연어를 주고 $N$개의 정점을 구입했다. 정점에는 $1$부터 $N$까지 번호가 적혀 있다. 흑곰은 $N$개의 정점을 상자에 담아 흰곰에게 주었고 흰곰은 상자를 들고 실험실로 돌아갔다.

흰곰은 $N$개의 정점을 가지고 이진 탐색 트리를 만드는 실험을 했다. 이진 탐색 트리는 많아야 하나의 왼쪽 자식과 많아야 하나의 오른쪽 자식을 갖는 트리이다. 임의의 정점 $x$에 대해 정점 $x$의 왼쪽 서브트리에는 $x$보다 작은 번호만 적혀있고 오른쪽 서브트리에는 $x$보다 큰 번호만 적혀있다.

흰곰의 연구 노트. 상자에서 $N$개의 정점을 꺼내 나열한다. 이는 수열 $X=\{x_1,x_2,\cdots ,x_N\}$으로 나타낼 수 있다. 정점 $x_1$을 루트로 정한다. 정점 $x_2,\cdots ,x_M$을 순서대로 트리에 추가한다. 과정이 진행되는 동안 트리는 항상 루트가 $x_1$인 이진 탐색 트리이다. 루트를 제외한 모든 정점의 부모 정점은 결정된 이후에 변하지 않는다.

정점 $u$와 정점 $v$를 잇는 경로에 포함된 간선의 개수를 $d(u,v)$라고 할 때 루트가 $x_1$인 트리의 높이는

\[H=\max_{1\le i\le N}{d(x_1,x_i)}\]

이다.

수열 $X=\{x_1,x_2,\cdots ,x_N\}$으로 만든 트리의 에너지는

\[E=\sum_{i=1}^{N}{\frac{x_i}{\left( N+1 \right)^{i-H}}}\]

이다.

흰곰은 $N!$ 번의 실험 끝에 에너지 $E$를 최소화하는 수열 $X$를 찾아냈고 이를 풀잎에 기록해두었다. 흰곰이 실험을 마치고 동굴에 들어가 잠에 든 사이에 토끼가 풀잎의 일부를 먹어버렸다. 잠에서 깬 흰곰을 이를 보고 슬퍼했고 토끼는 자신이 먹어 없어진 수열의 일부를 계산해서 흰곰에게 알려주기로 했다.

$M$개의 정수 $p_1,p_2,\cdots ,p_M$이 주어진다. 에너지 $E$를 최소화하는 수열 $X$에 대해 $x_{p_1},x_{p_2},\cdots ,x_{p_M}$을 구하시오.

입력

첫 번째 줄에 $N,M$이 공백으로 구분되어 주어진다. $(2\le N\le 10^{18};$ $1\le M\le\min(N,2\times 10^5) )$

두 번째 줄에 $p_1,p_2,\cdots ,p_M$이 공백으로 구분되어 주어진다. $(1\le p_i\le N;$ $p_i<p_{i+1})$

입력으로 주어지는 모든 수는 정수이다.

출력

첫 번째 줄에 $x_{p_1},x_{p_2},\cdots ,x_{p_M}$을 공백으로 구분하여 출력한다.

예제 입력 1

5 5
1 2 3 4 5

예제 출력 1

2 1 4 3 5

예제 입력 2

1000000000000000000 1
5

예제 출력 2

27222480487972865

출처

University > 경인지역 6개대학 연합 > shake! 2022 I번