최장 증가 부분 수열 길이 줄이기

시간 제한2초메모리 제한512 MB

요약

값이 1부터 k 사이인 정수 n개의 배열에서 가장 긴 증가하는 부분 수열의 길이가 k보다 작아지도록 지울 원소의 최소 개수와 그 번호를 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 그리디, 배열
정답자: 아직 제출이 없습니다

문제

길이가 $n$ 인 정수 배열이 있다. 배열의 각 원소 $a_i$ 는 $1$ 이상 $k$ 이하이다. 이 배열에서 가장 긴 증가하는 부분 수열의 길이가 $k$ 보다 작아지도록 하려면 최소 몇 개의 원소를 제거해야 하는가?

입력

첫 줄에 두 정수 $n$ 과 $k$ 가 주어진다 ( $1 \le n \le 10^6$ , $1 \le k \le n$ ). $n$ 은 배열의 길이이고, $k$ 는 배열 원소의 상한이다. 둘째 줄에는 $n$ 개의 정수 $a_i$ 가 주어진다 ( $1 \le a_i \le k$ ).

출력

첫 줄에 제거해야 하는 원소의 개수 $m$ 을 출력한다. 둘째 줄에는 제거할 원소의 번호 $m$ 개를 출력한다. 번호는 1부터 $n$ 까지이다.

예제3

예제 1
입력
```
3 2
1 2 2
```
예상 출력
```
1
1
```
예제 2
입력
```
2 2
2 1
```
예상 출력
```
0
```
예제 3
입력
```
8 3
1 2 2 1 1 3 2 3
```
예상 출력
```
2
1 7
```