Let's imagine that you're playing the following simple computer game. The screen…
- User
Let's imagine that you're playing the following simple computer game. The screen displays n lined-up cubes. Each cube is painted one of m colors. You are allowed to delete not more than k cubes (that do not necessarily go one after another). After that, the remaining cubes join together (so that the gaps are closed) and the system counts the score. The number of points you score equals to the length of the maximum sequence of cubes of the same color that follow consecutively. Write a program that determines the maximum possible number of points you can score.
Remember, you may delete no more than k any cubes. It is allowed not to delete cubes at all. Input
The first line contains three integers n, m and k (1 ≤ n ≤ 2·105, 1 ≤ m ≤ 105, 0 ≤ k < n). The second line contains n integers from 1 to m — the numbers of cube colors. The numbers of colors are separated by single spaces.
Output
Print the maximum possible number of points you can score.
Examples
Input
10 3 2 1 2 1 1 3 2 1 1 2 2
Output
4
Input
10 2 2 1 2 1 2 1 1 2 1 1 2
Output
5
Input
3 1 2 1 1 1
Output
3
Note
In the first sample you should delete the fifth and the sixth cubes.
In the second sample you should delete the fourth and the seventh cubes.
In the third sample you shouldn't delete any cubes.
Assistant
We need to solve: given an array of n integers (colors 1..m), we can delete up to k elements (any positions, not necessarily contiguous). After deletion, the remaining array is compressed (gaps removed), and the score is the length of the longest consecutive block of identical colors. We want to maximize this score.
We need to find maximum possible length L such that there exists a color c and a subarray (contiguous segment in original array) such that by deleting at most k elements from that segment (not from outside) we can obtain a contiguous block of color c of length L? Wait careful: The deletion is applied globally to the whole array. After deletions, we get a subsequence (preserving order) but we compress. The score is the length of the longest run of same color in that final sequence. So essentially, we are selecting a subsequence of the original array (by deleting some elements) and the subsequence has runs. We want to maximize the length of the longest run. Equivalent: we want to find a color c and a subsequence (preserving order) that consists of a block of L consecutive positions of color c (maybe after deletions we have that block) but also there may be other elements before/after; the block itself must be consecutive in the final sequence. In the final sequence, the run of color c will be formed by some set of positions from the original array that are all color c, and between any two of them there cannot be any other color (since they are consecutive). But if we delete all intervening non-c elements, then those c positions become adjacent. So essentially, for a given color c, we can pick a subsequence of c's and we can also include other colors? No, the run is only c's. For a run of L c's, we need to select L positions all of color c such that after deletion of all other elements between them, they become consecutive. But careful: If we select L c's that are not necessarily contiguous originally, we need to delete all elements (of any color) that lie between them in the original array to make them adjacent. However, we might also include other elements before or after but they must not be part of the run. So the run is a contiguous block in the final array consisting entirely of c's.
Thus, the problem reduces to: For each color c, consider the positions of color c in the array (sorted). We can choose a subsequence of these positions (i.e., a consecutive segment of these positions? Actually if we want to make a run of c's, we need to select a set of c positions that will become consecutive. Could they be non-consecutive in the original positions list? Suppose we have c positions at indices i1 < i2 < i3. If we delete all elements between i1 and i3 that are not c, and also we must ensure there are no other c's between i1 and i3 that we don't include? If we include i1 and i3 but not i2, then after deletions, we would have i1 then maybe other stuff? Actually if we delete all elements between i1 and i3 that are not c, but we left i2 (which is c) not selected? But we cannot "not select" i2 if it remains? The final subsequence consists of all elements that we did not delete. So if we don't delete i2, then it will appear in the final sequence. If we want a run of exactly L c's and we pick a set S of c positions, then we must ensure that in the final sequence, between any two selected c positions there are no other c positions (that we didn't delete) because that would be part of the run, thus increasing the run length, or breaking if we have other colors? Actually if we have c positions at i1, i2, i3 and we want to form a run of length L, we could select all three as part of the run; then we need to delete all elements between i1 and i3 that are not c, and then these three become consecutive. If we only select i1 and i3 but leave i2 not deleted, then i2 will still be in the final sequence. Since i1, i2, i3 are all c, after deleting non-c's, they will become consecutive and form a run of length 3, not 2. So we cannot selectively exclude c positions that lie between selected ones without deleting them. But we could delete i2 as well, but then we would lose that c. So if we want a run of exactly L c's, we must select a contiguous segment of c positions (in terms of the list of positions of color c) because any c between selected ones would either be included (if not deleted) making run longer, or would need to be deleted, which is wasteful (since we could include it to increase L without using extra deletions). So to maximize L with at most k deletions, we would want to include as many c's as possible. So we consider intervals of the array where we pick a contiguous block of c's (in the sense of positions list) and delete all other elements (non-c) that lie between the first and last selected c, and also possibly delete some c's outside? No, we want the run to be exactly that block of c's. So the cost in terms of deletions to form a run from the i-th occurrence to the j-th occurrence (inclusive) of color c is: the number of elements between positions pos[i] and pos[j] that are NOT of color c. Because we keep all c's in that segment? Actually we must keep all c's from i to j inclusive (since we want them in the run). We may also keep other colors? No, if we keep other colors, they would appear within the run breaking it. So we must delete all non-c elements in that segment. Additionally, we may also delete elements outside the segment, but those are not necessary for the run and we might have leftover deletions to use elsewhere but not needed for scoring because the run length is determined by the number of c's in the segment. However, we might also consider deleting some c's that are in the segment? That would reduce L, not beneficial. So to maximize L, for each color c we want the largest window [i, j] in its positions list such that the number of non-c elements between pos[i] and pos[j] is ≤ k (since we can delete at most k elements total, and we can allocate those deletions to remove those non-c elements). Also note: we are allowed to delete up to k elements globally, but we could also delete elements outside this window, but that doesn't affect the run. Since we want to maximize L, we can use all allowed deletions for cleaning the interior of the chosen segment. However, there might be other deletions needed? No, we can just delete exactly the non-c elements in that segment, and not delete anything else (or we could delete some extra but not needed). So the condition is that the number of non-c elements between first and last c in the segment is ≤ k. Then L = j - i + 1 (the count of c's in the segment). Also we must consider that the segment may be at the ends? That's fine.
But wait: is there any restriction on other runs? The score is the maximum run length in the final array. If we produce a run of length L, we don't care if there are other runs that might be longer? So we just need existence of a run of length L. So the above approach seems correct: For each color c, consider its positions sorted. For each window of positions (i..j), compute the number of non-c elements between pos[i] and pos[j]. That's equal to (pos[j] - pos[i] + 1) - (j - i + 1). Because total elements in the closed interval [pos[i], pos[j]] is (pos[j] - pos[i] + 1). Out of these, the c's are exactly (j - i + 1). So the number of other colors = (pos[j] - pos[i] + 1) - (j - i + 1). Let that be deletions_needed = (pos[j] - pos[i] + 1) - length, where length = j-i+1. We need deletions_needed ≤ k.
We want to maximize length.
Thus the problem reduces to: For each color, we have a sorted list of positions. For each left index i, we want to find the maximum j such that (pos[j] - pos[i] + 1) - (j - i + 1) ≤ k. That is, pos[j] - pos[i] + 1 - (j-i+1) ≤ k => pos[j] - pos[i] - (j - i) ≤ k => (pos[j] - j) - (pos[i] - i) ≤ k.
Let’s define transformed coordinate: For each occurrence of color c at position p, define value = p - index (where index is the order in the list, starting from 0). Then for a window from i to j, condition becomes (p_j - j) - (p_i - i) ≤ k.
Since the list is sorted, p_j increases with j. Also p_j - j is non-decreasing? p_j increases by at least 1 each step, j increases by 1, so p_j - j is non-decreasing? Actually p_j >= p_{j-1}+1, so p_j - j >= p_{j-1} - (j-1) is? Let's compute: p_j - j - (p_{j-1} - (j-1)) = (p_j - p_{j-1}) - 1. Since p_j - p_{j-1} >= 1, the difference is at least 0. So indeed p_j - j is non-decreasing. So the transformed sequence is non-decreasing. Good.
Thus for each i, we want to find the largest j such that t_j - t_i ≤ k, where t_x = p_x - x. Since t is non-decreasing, we can use two pointers (sliding window) to find max length for each color.
Specifically, for a given color, we have positions list pos[0..len-1]. Compute t[i] = pos[i] - i. Then for each left pointer l, we extend right pointer r as far as possible such that t[r] - t[l] ≤ k. Then the length = r - l + 1 is a candidate. Since t is non-decreasing, we can slide l from 0 to len-1 and maintain r accordingly (move r forward as much as possible). This gives O(len) per color. Sum over all colors len = n, so O(n) total.
Edge cases: k can be zero. Then condition is t[r] - t[l] ≤ 0 => t[r] = t[l] => that means p[r] - r = p[l] - l => p[r] - p[l] = r - l => number of elements between positions equals number of c's -1? Actually condition is (p[r] - p[l] +1) - (r-l+1) = 0 => there are no non-c elements between p[l] and p[r], meaning all positions between them are also c's. So the segment of c's is contiguous in the array, as expected. So algorithm works.
Now we must also consider possibility that we could achieve a longer run by also including c's from outside the segment but after deleting some c's? No, as argued, we wouldn't delete c's because they increase run length; but what about if we have two separate blocks of c's with many non-c between them. To combine them into one run, we need to delete all non-c between them, which is exactly the condition. And we should include all c's from both blocks (since they increase run). So yes.
But is there any nuance about deletions of elements before the first c or after the last c? Those deletions don't affect the run length, but they count towards k. However, we might use deletions that are not strictly needed for the interior of the segment. Since we have a budget of up to k deletions, we can allocate them to delete interior non-c. Deleting elements outside does not help the run, but could be used if we need to delete something? No, we only have limit, not requirement to delete exactly k. So we only need ≤ k. So we can ignore outside.
Thus algorithm: For each color (1..m), collect its positions. For each such list, do two-pointer to find max length such that t[r] - t[l] ≤ k. Keep global maximum.
Complexities: n up to 2e5, m up to 1e5, but sum of lengths across colors = n. So we can store positions in vector per color, using dictionary/map or array of vectors (since m up to 1e5, we can allocate vector colors[m+1] but m maybe 1e5, total n=2e5, fine). Use 1-indexing? Input colors from 1 to m, n positions.
Implementation details: read n, m, k. Then for i from 1 to n (or 0-index), read color x, push i (1-indexed) into list for color x. Then iterate over colors 1..m. For each list with size at least 1, compute t array: for index idx from 0 to size-1, t[idx] = pos[idx] - idx (where pos is 1-indexed). Actually careful: When using positions 1-indexed, the index in list is 0-indexed. Then condition: (pos[j] - pos[i] +1) - (j-i+1) ≤ k => pos[j] - pos[i] - (j-i) ≤ k. Let i, j be list indices. Then let i index correspond to position p_i, j to p_j. Then t_i = p_i - i. Using 0-index i, we have: p_j - p_i - (j - i) = (p_j - j) - (p_i - i) = t_j - t_i. So t_i = p_i - i, where i is 0-index. Since p_i are >=1, and i starts at 0. Works.
Two-pointer: l = 0, r = 0. While r < len: we want to extend r as far as possible. Actually typical sliding window: for each l, we move r to max such that condition holds. Since t is non-decreasing, we can maintain r pointer globally. Initialize r = 0. For l from 0 to len-1: while r+1 < len and t[r+1] - t[l] ≤ k: r += 1 Then window length = r - l + 1 is candidate. Then l increments; but r should never go backward; if r < l, set r = l.
But careful: When l increases, condition may become false for current r? Actually t[r] - t[l] decreases because t[l] increased (since t is non-decreasing, t[l+1] >= t[l], so t[r] - t[l+1] ≤ t[r] - t[l] maybe smaller? Wait: t[r] - t[l+1] ≤ t[r] - t[l] because t[l+1] >= t[l]. So if it was ≤ k before, it's still ≤ k? Actually subtracting a larger number makes difference smaller, so condition might become even more satisfied. So when l increases, the condition t[r] - t[l+1] ≤ k might still hold. But there is nuance: if we had r such that t[r] - t[l] ≤ k, then t[r] - t[l+1] could be ≤ k as well because t[l+1] >= t[l], so difference smaller or equal. So condition remains satisfied. So r can stay or maybe we can even increase further. So sliding window works fine: we can for each l, extend r while condition holds.
But need to ensure that when l increments, if r < l then set r = l.
So algorithm per list:
len = list.size() if len == 0: continue. Create vector t of length len: for i in range(len): t[i] = list[i] - i // since list[i] is 1-indexed Initialize r = 0, ans_color = 1 (at least 1 because we have at least one cube) For l in 0..len-1: if r < l: r = l while r+1 < len and t[r+1] - t[l] <= k: r += 1 ans_color = max(ans_color, r - l + 1)
global_ans = max(global_ans, ans_color)
Finally print global_ans.
Check with examples:
Example 1: n=10, k=2. colors: 1 2 1 1 3 2 1 1 2 2 Let's compute for color 1: positions: 1,3,4,7,8? Actually list: index1? Use 1-index: positions: 1? (color1 at pos1), pos2? color2, pos3 color1, pos4 color1, pos5 color3, pos6 color2, pos7 color1, pos8 color1, pos9 color2, pos10 color2. So color1 positions: [1,3,4,7,8] (5 occurrences). t = [1-0=1, 3-1=2, 4-2=2, 7-3=4, 8-4=4] => [1,2,2,4,4]. Now k=2. Two-pointer: l=0, r start 0: t[0]-t[0]=0 <=2, extend: check r+1=1: t[1]-t[0]=2-1=1 <=2 -> r=1; r=1, check r+1=2: t[2]-t[0]=2-1=1 <=2 -> r=2; r=2, check r+1=3: t[3]-t[0]=4-1=3 >2 stop. So window length=3 (indices0-2) -> length=3. (positions 1,3,4; between them non-c count? pos4-pos1+1=4, c count=3, deletions needed=1, which is <=2. Could we include also pos7? That would need deletions: between pos1 and pos7: total=7, c's=4? Actually positions1,3,4,7 -> total 7-1+1=7, c count=4, deletions=3 >2, so not allowed.) l=1: r currently 2; condition t[2]-t[1]=2-2=0 <=2, okay. Try extend: r+1=3: t[3]-t[1]=4-2=2 <=2 -> r=3; now r=3, check r+1=4: t[4]-t[1]=4-2=2 <=2 -> r=4; now r=4, check r+1 none. So window length = 4-1+1 = 4 (indices1-4). That's length=4. For l=1: positions 3,4,7,8; total from 3 to 8 inclusive: 8-3+1=6, c count=4, deletions=2 <=2. So ans_color=4. l=2: r=4; t[4]-t[2]=4-2=2 <=2, good; try extend r+1 none; window length=4-2+1=3. l=3: r=4; t[4]-t[3]=4-4=0 <=2; window length=2. l=4: window length=1. So max for color1 is 4.
Color2 positions: [2,6,9,10]? Actually positions:2,6,9,10 => [2,6,9,10]. t: [2-0=2, 6-1=5, 9-2=7,10-3=7]. k=2. l=0: r can go to? t[1]-t[0]=3<=2? 5-2=3 >2, so only r=0 -> length1. l=1: r=1; can extend? t[2]-t[1]=7-5=2 <=2 -> r=2; then t[3]-t[1]=7-5=2 <=2 -> r=3; length=3 (indices1-3) => positions6,9,10: from 6 to10: total5, c count=3, deletions=2 <=2 -> length3. l=2: window maybe length2 or 3? l=2: r=3; t[3]-t[2]=7-7=0 <=2 => length2. l=3: length1. So max for color2 =3. Color3 positions: [5] -> max1. Global max =4. matches example output 4.
Example2: n=10 k=2 colors: 1 2 1 2 1 1 2 1 1 2 Let's compute. Color1 positions: 1,3,5,6,8,9? Actually: pos1:1 2:2 3:1 4:2 5:1 6:1 7:2 8:1 9:1 10:2 So color1: [1,3,5,6,8,9] (6 occurrences). t: [1-0=1, 3-1=2, 5-2=3, 6-3=3, 8-4=4, 9-5=4] => [1,2,3,3,4,4]. k=2. Two-pointer: l=0: r extend: t[1]-t[0]=1 <=2 -> r=1; t[2]-t[0]=2 <=2 -> r=2; t[3]-t[0]=3-1=2 <=2 -> r=3; t[4]-t[0]=4-1=3 >2 stop. So window indices0-3 length=4 (positions1,3,5,6). Check deletions: from pos1 to6: total6, c count=4, deletions=2 <=2. Could we include pos8? That would be positions1..8: total8, c count=5? Actually include pos8? index4? But we stopped at index3, index4 (pos8) t[4]-t[0]=4-1=3 >2, so not allowed. l=1: r currently3; t[3]-t[1]=3-2=1 <=2, extend? t[4]-t[1]=4-2=2 <=2 -> r=4; t[5]-t[1]=4-2=2 <=2 -> r=5. So window indices1-5 length=5 (positions3,5,6,8,9). Check: from pos3 to9: total7, c count=5, deletions=2 <=2. So ans=5. l=2: r=5; t[5]-t[2]=4-3=1 <=2, window length=4? indices2-5 =4. So max=5. Color2 positions: [2,4,7,10] => t: [2-0=2,4-1=3,7-2=5,10-3=7] => [2,3,5,7]. k=2. l=0: max r? t[1]-t[0]=1<=2->r=1; t[2]-t[0]=3 >2 stop -> length2 (positions2,4: from2 to4 total3, c count2, deletions1) l=1: maybe length3? t[2]-t[1]=2<=2 -> r=2; t[3]-t[1]=4>2 stop -> length2? Actually indices1-2 length2? Wait r start? Let's do properly: l=1, start r=1? We'll use sliding window: after l=0, r=1. Then l=1: r currently1, but we can extend: check r+1=2: t[2]-t[1]=5-3=2 <=2 -> r=2; check r+1=3: t[3]-t[1]=7-3=4>2 stop -> window length=2? indices1-2 => length2? Actually indices1,2 => two elements, but we might also include index? No, it's positions4 and7? Actually indices:0:2,1:4,2:7,3:10. So window from 1 to2 includes two positions (4 and7). Could we get 3? For l=0 we got 2. For l=1 we got 2. l=2 we get maybe length2? So max 2. Thus global max =5. matches example.
Example3: n=3 k=2 colors all 1. positions [1,2,3], t: [1,1,1]? Actually: i=0:1-0=1; i=1:2-1=1; i=2:3-2=1. All 1. k=2. Two-pointer: l=0: r can extend to 2 because t[2]-t[0]=0<=2. length=3. So answer 3.
Thus algorithm works.
But wait: Is there any scenario where we might want to delete some c's from the interior of a segment to reduce the number of deletions needed? That seems counterproductive because we are trying to maximize run length. But maybe if the deletions of non-c are too many, we could skip some c's to reduce the span and thus require fewer deletions, and the resulting run might be longer than a run that includes them? Actually if we skip c's, we would have fewer c's, so length decreases. So not beneficial.
But there is another nuance: The run we form might be not necessarily from a contiguous block of c's in the original positions list? Suppose we have color c at positions: 1,2,4,5. To get a run of length 4, we need to delete position 3 (non-c). That's fine. Now suppose we have positions: 1,3,5,7, and many non-c between. To get a run of length 4, we need to delete positions 2,4,6 (non-c) = 3 deletions. That's exactly t condition. So always contiguous in the list.
But what about using deletions to also delete some c's to allow merging of larger blocks? For example, we could have two blocks of c's separated by some c's that we delete? Actually if we delete some c's, we might be able to join other c's? No, because if we delete intervening c's, they won't be part of the run; but maybe if the intervening c's are few and the non-c's are many, we could delete both some c's and non-c's to achieve a longer run? That doesn't make sense: deleting c's reduces the number of c's in the run, so not helpful.
Alternatively, could we achieve a run longer than the number of c's in a contiguous segment by including c's from both sides after deleting some c's? No, run length is number of consecutive c's, which cannot exceed total number of c's kept in that segment.
Thus the approach is correct.
But wait: There is also possibility of using deletions to remove elements that are not between the first and last c but are between other c's? Already accounted.
Edge cases: k can be up to n-1. So we can delete almost all. Then the maximum possible run length is the total count of the most frequent color, because we could delete all other colors and also possibly some c's? Actually we don't need to delete c's. So we can take all c's of a color and delete everything else, achieving a run equal to the count of that color. But note: If we delete all non-c, the c's will be consecutive, so run length = total count of that color. So maximum possible is max frequency of any color. But our algorithm will find that because for a color with freq f, the whole list from i=0 to j=f-1 has deletions_needed = (pos[last] - pos[first] +1) - f. If we can delete all non-c in that entire span, but we might need to delete more than k if the span is large. However, if we delete all elements except the c's globally, we need deletions = n - f. That might be ≤ k? But in our window method, we only delete non-c between first and last c. If we take the entire list of c's, we only delete non-c within the range from first to last. What about non-c outside that range? They are not between the first and last c, so they would still be present in the final array, possibly before or after the run. That's okay; they don't affect the run length, as they are not inside the run. But they might be present and count as deletions? Actually we are allowed to delete up to k; we don't have to delete them. So we can keep them, they won't break the run because they are outside the run (they will be placed either before or after the block). However, if we keep non-c elements before the first c, then in the final array the run of c's will start after those elements, but still contiguous block of c's exists. So we don't need to delete elements outside the chosen window. So the minimal deletions needed to achieve a run of all f c's is the number of non-c's between the first and last c, not the total non-c's globally. So it's possible that even if n - f > k, we might still achieve f if the first and last c are close together relative to f. Example: Suppose array: c at positions 1 and 100, with many other colors between, and also many c's elsewhere? Actually f is total count of c, but if first and last c are far apart, then deletions_needed = (last