28382번 - Yet Another Problem on Empodia 2 스페셜 저지

길이 $n$의 순열 $p_1, p_2, \ldots, p_n$ 에 대해, 어떠한 연속 부분 수열 $p_l, p_{l + 1}, \ldots, p_r$ ($1 \le l\le r \le n$) 이 $\max_{k = l}^{r} p_k - \min_{k = l}^{r} p_k = r - l$ 을 만족한다면 이를 프레임 구간 (framed interval) 이라고 부른다. 예를 들어 $[7, 8, 9], [3, 1, 5, 4, 2], [4, 3], [2]$ 은 프레임 구간이다. $[3, 5], [5, 3]$ 은 프레임 구간이 아니다.

구사과는 길이 $n$ 의 순열을 잡고 $p_l, p_{l + 1}, \ldots, p_r$ 이 프레임 구간을 이루는 순서쌍 $(l, r)$ ($1 \le l \le r \le n$) 의 수를 세고 있었다.

하지만 서울대학교 화학부 종신교수 윤창기가 순열을 불태워버렸다. 불태운 이후, 순열의 앞 $k$ 개 수만이 남았다.

구사과를 도와, 순열의 맨 앞 $k$ 개 원소가 주어졌을 때, 나머지 수를 최적으로 채워 프레임 구간의 개수를 최대화하여야 하고, 그러한 순열 중 하나를 아무거나 출력해야 한다.

첫 번째 줄에 두 정수 $n, k$ 이 주어진다. ($1 \le n \le 200\,000, 0 \le k \le n$)

두 번째 줄에 $k$ 개의 정수 $p_i$ 가 주어진다. ($1 \le p_i \le n$) 만약 $k = 0$ 일 경우 이 줄은 빈 줄로 주어진다.

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

첫 번째 줄에 가능한 프레임 구간의 최대 개수를 하나의 정수로 출력하라.

두 번째 줄에 최적 순열을 이루는 $n$ 개의 정수를 출력하라. 순열의 앞 $k$ 개 원소가 입력과 일치해야 한다.