You are given array a a of length n n . You can choose one segment [l,r] [l,r] (1≤l≤r≤n 1≤l≤r≤n ) and integer value k k (positive, negative or even zero) and change a l ,a l+1 ,…,a r al,al+1,…,ar by k k each (i.e. a i :=a i +k ai:=ai+k for each l≤i≤r l≤i≤r ).
What is the maximum possible number of elements with value c c that can be obtained after one such operation?
Input
The first line contains two integers n n and c c (1≤n≤5⋅10 5 1≤n≤5⋅105 , 1≤c≤5⋅10 5 1≤c≤5⋅105 ) — the length of array and the value c c to obtain.
The second line contains n n integers a 1 ,a 2 ,…,a n a1,a2,…,an (1≤a i ≤5⋅10 5 1≤ai≤5⋅105 ) — array a a .
Output
Print one integer — the maximum possible number of elements with value c c which can be obtained after performing operation described above.
Examples
6 9
9 9 9 9 9 9
6
3 2
6 2 6
2
题意：给定长度位N的序列，以及数字C，现在你可以给某个区间加一个数，使得最后这个序列的C个数最大，输出这个个数。
思路：假设我们在[L,R]这个区间加一个数(不为0)，那么最后这个区间的贡献显然是众数减去这个区间原本为C的个数。
显然相同的数字一同考虑，考虑其贡献：每个数的贡献为1-到前一个的C的个数。
比如C=2； 那么1,2,3,2,1,5，第一个1的贡献是1，第二个1的贡献是-1，因为中间夹了两个C，即如果我们把1变为C，那么增加了一个C(1)，但是减少了两个C(2)。
我们把每个数的贡献放到对应的数组里，然后就求“最大连续区间和”res。
而求最大连续区间和的过程，如果当前sum<1，舍去前一段，令sum=1，因为第一个pre是肯定可以做贡献为1的。 这里我wa了两发。其他地方还是蛮好想的。
下面的代码为为了避免负数，所有都加了一个Z=500000。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int a[maxn],b[maxn],Laxt[maxn],ans,N,C,res;
vector<int>G[maxn];
int main()
{
scanf("%d%d",&N,&C); int Z=;
rep(i,,N) scanf("%d",&a[i]),a[i]=a[i]-C+Z;
rep(i,,N) {
b[i]=b[i-]; if(a[i]==Z) b[i]++;
int pre=Laxt[a[i]]; if(pre==) pre=i;
G[a[i]].push_back(-b[i]+b[pre]);
Laxt[a[i]]=i;
}
ans=b[N];
rep(i,,maxn-) {
if(i==Z) continue;
int tmp=;
for(int j=;j<G[i].size();j++){
tmp+=G[i][j];
res=max(tmp,res);
if(tmp<=) tmp=;
}
}
printf("%d\n",ans+res);
return ; }
//8 4 4 0 0 4 2 1 0 4
//12 1 1 0 1 0 1 1 1 0 0 1 1 0