[思维][双指针]Klee in Solitary Confinement 2021年ICPC南京站C

Since the traveler comes, People in Monstadt suddenly raise great interest in computer programming and algorithms, including Klee, the Spark Knight of the Knights of Favonius.

Source: Genshin Impact Official

Being sent to solitary confinement by Jean again, Klee decides to spend time learning the famous Mo's algorithm, which can compute with a time complexity of O(n1.5)O(n1.5) for some range query problem without modifications.

To check whether Klee has truly mastered the algorithm (or in fact making another bombs secretly), Jean gives her a problem of an integer sequence a1,a2,⋯,ana1,a2,⋯,an along with some queries [li,ri][li,ri] requiring her to find the mode number in the contiguous subsequence ali,ali+1,⋯,ariali,ali+1,⋯,ari. The mode number is the most common number (that is to say, the number which appears the maximum number of times) in the subsequence.

With the help of Mo's algorithm, Klee solves that problem without effort, but another problem comes into her mind. Given an integer sequence a1,a2,⋯,ana1,a2,⋯,an of length nn and an integer kk, you can perform the following operation at most once: Choose two integers ll and rr such that 1≤l≤r≤n1≤l≤r≤n and add kk to every aiai where l≤i≤rl≤i≤r. Note that it is OK not to perform this operation. Compute the maximum occurrence of the mode number of the whole sequence if you choose to perform (or not perform) the operation optimally.

Input

There is only one test case in each test file.

The first line of the input contains two integers nn and kk (1≤n≤1061≤n≤106, −106≤k≤106−106≤k≤106) indicating the length of the sequence and the additive number.

The second line of the input contains nn integers a1,a2,⋯,ana1,a2,⋯,an (−106≤ai≤106−106≤ai≤106) indicating the original sequence.

Output

Output one line containing one integer indicating the maximum occurrence of the mode number of the whole sequence after performing (or not performing) the operation.

Examples

input

5 2
2 2 4 4 4

output

5

input

7 1
3 2 3 2 2 2 3

output

6

input

7 1
2 3 2 3 2 3 3

output 

5

input

9 -100
-1 -2 1 2 -1 -2 1 -2 1

output

3

题意： 有一个长度为n的数组a，以及一个参数k，现在要求整个数组中出现次数最多的那个数的出现次数。你可以进行1次或0次操作，操作内容是任选一个区间[l, r]并让每个数+k，问最终答案是多少。

分析： 可以对原数组中每个数字存储下来它出现的位置，方便起见用vector数组存储，a[i]表示i这个数字在原数组中出现在全部位置，然后枚举原数组中的每个数i，求出i+k的最大出现次数，具体过程是一个双指针，一个指针维护i出现的位置，一个指针维护i+k出现的位置，一开始i+k出现次数一定是a[i+k].size()，设num为i+k出现次数，那么初始时num = a[i+k].size()，之后按照原数组中先后顺序移动双指针，当遇到i时num++并记录最大出现次数，当遇到i+k时num--并且num不能减到小于a[i+k].size()，因为即使不操作也能获得a[i+k].size()个i+k，当扫描完全部数字后就得到了答案，总时间复杂度为O(n)。最后需要注意n == 1的情况和k == 0的情况。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
vector<int> a[3000005];
 
signed main()
{
	int n, k;
	scanf("%d%d", &n ,&k);
	for(int i = 1; i <= n; i++){
		int t;
		scanf("%d", &t);
		t += 2e6+1;
		a[t].push_back(i);
	}	
	int ans = 0;
	for(int i = 1; i <= 3000001; i++){
		if(a[i].size() && k != 0){
			int mx = 0;
			if(i+k <= 3000001 && a[i+k].size() != 0){
				int num = a[i+k].size();
				int x = 0, y = 0;
				while(x < a[i].size() || y < a[i+k].size()){
					if(x == a[i].size()){
						y++;
					}
					else if(y == a[i+k].size()){
						x++;
						num++;
						mx = max(num, mx);
					}
					else if(a[i][x] < a[i+k][y]){
						x++;
						num++; 
						mx = max(num, mx);
					}
					else{
						if(a[i+k][y] > a[i][0]){
							num--;
							num = max(num, (int)a[i+k].size()); 
						}
						y++;
					}
				}
				mx = max(num, mx);
			}
			ans = max(ans, mx);
		}
		ans = max(ans, (int)a[i].size());
	}
	printf("%d\n", ans);
	return 0;
}