철도 운송

ACM이 새로운 대형 광고판 시리즈를 제작했고, 이 광고판들을 기차로 운송해야 합니다. 광고판은 각각 화차(carriage)에 실리는데, 화차들이 뒤섞인 순서로 조차장에 도착합니다. 하지만 ACM은 이들이 정해진 순서대로 배달되기를 원합니다.

조차장에는 $M$개의 평행한 선로가 있습니다. 화차는 한 번에 하나씩 들어오며, 각 화차는 이 선로들 중 어느 하나로 보낼 수 있습니다. 화차가 일단 어떤 선로에 들어가면 앞으로만 갈 수 있고 절대 뒤로 되돌아갈 수 없습니다. 반대쪽 끝에서 모든 선로는 하나의 출구 선로로 합쳐지며, 여기서도 화차는 앞으로만 이동할 수 있습니다. 화차는 절대 후진할 수 없으므로, 한 선로 위의 화차들은 그 선로에 들어간 순서 그대로 그 선로를 빠져나갑니다.

우리는 화차들이 목표 번호의 비내림차순(오름차순, 같은 값 허용)로 조차장을 떠나기를 원합니다. 화차들은 입력에 주어진 순서대로 도착하며, $i$번째 수는 $i$번째로 도착하는 화차의 목표 값입니다. 번호가 같은 화차들끼리는 서로 어떤 순서로 나가도 상관없습니다. 선로는 화차를 몇 개든 담을 수 있을 만큼 충분히 깁니다.

입력은 여러 개의 시나리오로 이루어집니다. 각 시나리오는 두 줄로 주어지며, 입력의 끝은 두 개의 0이 적힌 줄로 표시됩니다.

각 시나리오의 첫 번째 줄에는 공백으로 구분된 두 정수 $N$과 $M$이 주어집니다($1 \le N \le 200000$, $1 \le M \le 200000$). $N$은 화차의 수, $M$은 선로의 수입니다.

두 번째 줄에는 $N$개의 음이 아닌 정수가 주어지며, 이는 화차들이 도착하는 순서대로 나열한 목표 값입니다. 일부 값은 같을 수 있으며, 그 경우 해당 화차들 사이의 순서는 중요하지 않습니다.

각 시나리오마다 한 줄을 출력합니다.

모든 선로는 화차가 들어온 순서 그대로 화차를 내보내므로, 한 선로에 배정된 화차들은 이미 비내림차순으로 정렬되어 있어야 합니다. 따라서 화차들을 $M$개의 선로로 비내림차순으로 배달할 수 있는 것은, 도착 순서 기준으로 각각 비내림차순인 최대 $M$개의 그룹으로 나눌 수 있을 때와 정확히 같습니다.

모든 화차를 비내림차순으로 배달하는 데 필요한 최소 선로 수를 출력하세요. 만약 이 최소 값이 $M$보다 크면 주어진 선로로는 배달이 불가능하며, 이 경우 대신 Transportation failed를 출력하세요.