시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB226766538.462%

문제

$1$부터 $N$까지의 수가 하나씩 임의로 배열된 길이 $N$의 수열 $A_1, A_2,..., A_N$이 주어진다. 주어진 수열에서 연속된 $K$개의 수를 고른 후, 선택한 $K$개의 수의 구간 내에서 $K$개의 수를 자유롭게 재배열하는 연산을 한 번 수행한다.

연산을 수행한 후, 수열에서 만들 수 있는 연속된 증가하는 부분 수열의 최대 길이를 구하시오.

증가하는 수열이란, 모든 $i < j$에 대해 $A_i < A_j$인 수열을 말한다.

입력

첫 번째 줄에 정수 $N$, $K$가 공백으로 구분되어 주어진다.

두 번째 줄에 정수 $A_1, A_2, ..., A_N$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 수열에서 만들 수 있는 연속된 증가하는 부분 수열의 최대 길이를 출력한다.

제한

  • $3 \leq N \leq 2\,000$
  • $2 \leq K \leq N$
  • $1 \leq A_i \leq N$

서브태스크

번호배점제한
140

$N \leq 10$

260

추가적인 제약 조건이 없다.

예제 입력 1

5 3
2 1 5 3 4

예제 출력 1

4

예제 입력 2

7 3
3 2 1 7 4 5 6

예제 출력 2

5

채점 및 기타 정보

  • 예제는 채점하지 않는다.