시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 7 | 6 | 6 | 85.714% |
The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous.
You are given a permutation of the first n positive integers a1, a2, . . . , an and an integer k. Your task is to find, for each i from 1 to n − k + 1, the length of the longest increasing subsequence of the sequence a1, a2, . . . , ai−1, ai+k, ai+k+1, . . . , an (in other words, the sequence obtained by erasing ai, ai+1, . . . , ai+k−1 from a).
The first line of the input contains two integers n and k (1 ≤ k < n ≤ 3 · 105), denoting the length of the given permutation and the number of consecutive elements to be removed.
The second line contains n integers a1, a2, . . . , an (1 ≤ ai ≤ n; ai ≠ aj for i ≠ j), denoting the elements of the permutation.
Display n−k+1 integers, one per line, where the i-th integer denotes the length of the longest increasing subsequence of the sequence a1, a2, . . . , ai−1, ai+k, ai+k+1, . . . , an for i = 1, 2, . . . , n − k + 1.
8 3 6 5 3 1 8 2 4 7
4 3 3 3 2 2