You are given array $a$ of length $n$. You can choose one segment $[l, r]$ ($1 \le l \le r \le n$) and integer value $k$ (positive, negative or even zero) and change $a_l, a_{l + 1}, \dots, a_r$ by $k$ each (i.e. $a_i := a_i + k$ for each $l \le i \le r$).

What is the maximum possible number of elements with value $c$ that can be obtained after one such operation?


-----Input-----

The first line contains two integers $n$ and $c$ ($1 \le n \le 5 \cdot 10^5$, $1 \le c \le 5 \cdot 10^5$) — the length of array and the value $c$ to obtain.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 5 \cdot 10^5$) — array $a$.


-----Output-----

Print one integer — the maximum possible number of elements with value $c$ which can be obtained after performing operation described above.


-----Examples-----
Input
6 9
9 9 9 9 9 9

Output
6

Input
3 2
6 2 6

Output
2



-----Note-----

In the first example we can choose any segment and $k = 0$. The array will stay same.

In the second example we can choose segment $[1, 3]$ and $k = -4$. The array will become $[2, -2, 2]$.

Difficulty: interview

Starter code:

Solutions:
n, c = list(map(int, input().split()))
res1 = [0] * 500001
res = 0
for ai in map(int, input().split()):
	res1[ai] = max(res1[ai], res1[c])
	res1[ai] += 1
	res = max(res, res1[ai] - res1[c])
print(res + res1[c])


from collections import defaultdict

def solve():
    N, C = map(int, input().split())
    
    arr = [int(k) for k in input().split()]
    
    cnt = 0
    best = 0
    freq = defaultdict(int)
    
    for i in range(N):
        freq[arr[i]] = max(freq[arr[i]], freq[C])
        '''
        if arr[i] == C:
            cnt += 1
            if freq:
                cur = max(freq.values())
                if cur > best:
                    best = cur
                
                freq = defaultdict(int)
            continue
        '''
        freq[arr[i]] += 1
        cur = freq[arr[i]] - freq[C]
        if cur > best:
            best = cur
                    
    print (best + freq[C])

    
solve()

n, c = list(map(int, input().split()))
cnt = [0] * 500005
ans = 0
for v in map(int, input().split()):
    if v == c:
        cnt[c] = cnt[c] + 1
    else:
        if cnt[v] < cnt[c]:
            cnt[v] = cnt[c]
        cnt[v] += 1
    ans = max(ans, cnt[v] - cnt[c])
print(ans + cnt[c])


n,c=list(map(int,input().split()))
a=list(map(int,input().split()))


# ça ne coûte pas trop cher de transformer le problème.

nc = 0
last = {}
preconfs = []
preconfc = []
for i in range(n) :
	if a[i] == c :
		nc += 1
		last[c] = i
		preconfs.append ( i )
	else :
		if not (a[i] in last) :
			preconfs.append ( 1 )
		else :
			preconfs.append ( preconfs[last[a[i]]] + 1 )
		last[a[i]] = i
	preconfc.append ( nc )

# deuxième transfo

content = {}
for i in range(n) :
	if a[i] in content :
		content[a[i]][0] += 1
		content[a[i]].append ( i )
	else :
		content[a[i]] = [1, i]

def val ( i, j ) :
	if a[i] == a[j] :
		return nc + (preconfs[j]-preconfs[i]+1) - (preconfc[j]-preconfc[i]) + (a[i]==c and -1 or 0)
	print( "erreur" )

def rec_sol ( i, j, tab ) :
	if (i==j) :
		return (i,i,j,j)

	k = (i+j)//2
	r1 = rec_sol ( i, k, tab )
	r2 = rec_sol ( k+1, j, tab )

	i1 = max ( [r1[0], r2[0]], key = lambda x:val(tab[x], tab[j]) )
	i2, i3 = max ( [(r1[0],r2[3]), (r1[1],r1[2]), (r2[1],r2[2]), (r1[0],j)], key = lambda x : val(tab[x[0]],tab[x[1]]) )
	i4 = max ( [r1[3], r2[3]], key = lambda x:val(tab[i],tab[x]) )
	return (i1,i2,i3,i4)


def get_sol ( k ) :
	s = rec_sol ( 1, content[k][0], content[k] )
	return val ( content[k][s[1]], content[k][s[2]] )

res = []
for i in content :
	if ( i != c ) :
		res.append ( get_sol ( i  ) )
if res :
	print ( max ( res ) )
else :
	print ( n )

n,tar=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]

from collections import defaultdict
d=defaultdict(lambda:[])
count=0
for i in range(n):
    d[a[i]].append(i)
    if a[i]==tar:
        count+=1

presum=[1 if a[0]==tar else 0]
for e in a[1:]:
    if e==tar:
        presum.append(presum[-1]+1)
    else:
        presum.append(presum[-1])

final = 0
for k,v in d.items():
    if k==tar:
        continue

    t=1
    tt=1
    for i in range(1,len(v)):
        ind=v[i]
        preind=v[i-1]

        t -= presum[ind] - presum[preind]
        t=max(t,0)
        t+=1
        tt=max(tt,t)

    final=max(final,tt)

print(final + count)

t=list(map(int,input().split()))
n=t[0]
c=t[1]
a=list(map(int,input().split()))
f=[]
for i in range(0,500001):
	f.append(0)
l=[]
for i in range(0,500001):
	l.append([0])
m=0
for i in range(n):
	l[a[i]].append(f[a[i]]-m)
	if a[i]==c:
		m+=1
	f[a[i]]+=1
	l[a[i]].append(f[a[i]]-m)
ma=0
for i in l:
	mi=0
	for j in i:
		if(j<mi):
			mi=j
		if(ma<j-mi):
			ma=j-mi
print(m+ma)

n,val=map(int,input().split());
a=[0]+list(map(int,input().split()));
suma=[0 for i in range(n+1)];
mx=0;
target=0;
for i in range(1,n+1):
	suma[i]=suma[i-1];
	mx=max(mx,a[i]);
	if (a[i]==val):
		target+=1;
		suma[i]+=1;

ans=0;
pre=[0 for i in range(mx+1)];
dp=[0];
for i in range(1,n+1):
	dp.append(max(1,1+dp[pre[a[i]]]-suma[i]+suma[pre[a[i]]]));
	if (a[i]!=val):
		ans=max(ans,dp[i]);
	pre[a[i]]=i;
print(ans+target);

n,c = list(map(int,input().split(" ")))
nums = list(map(int,input().split(" ")))
# c is the target number
# number of c values seen
cPast = 0
countC = 0

for value in nums:
	if value == c:
		countC += 1

def sawC(groupsList):
	for key,groups in list(groupsList.items()):
		if groups[-1] < 0:
			groups[-1] -= 1
		else:
			groups += [-1]
	return groupsList

solution = countC
#other numbers, highest count stored in hash table
groupsList = {}
for num in nums:
	if num == c:
		groupsList = sawC(groupsList)
	elif num in list(groupsList.keys()):
		if groupsList[num][-1] > 0:
			groupsList[num][-1] += 1
		else:
			groupsList[num] += [1]
	else:
		groupsList[num] = [1]

for key,groups in list(groupsList.items()):
	# actually counting if good
	#print("groups: ",groups)
	maxDiff = 1
	currDiff = 0
	newDiff = 0
	for group in groups:
		currDiff += group
		if group > currDiff:
			currDiff = group
		if currDiff > maxDiff:
			maxDiff = currDiff
	if maxDiff + countC > solution:
		solution = countC + maxDiff
print(solution)
	
						
			









# coding=utf-8

n, c = map(int, input().split())

ans = [0] * 500001
res = 0

for i in map(int, input().split()):
    ans[i] = max(ans[i], ans[c])
    ans[i] += 1
    res = max(res, ans[i] - ans[c])

print(res + ans[c])

n,c=map(int,input().split())
a=list(map(int,input().split()))
cs=0
x=a.count(c)
best=[x]*5000001
curr=[x]*5000001
rec=[0]*5000001
for i in range(n):
    if a[i]==c:
        cs+=1
    else:
        curr[a[i]]=max(x,curr[a[i]]+rec[a[i]]-cs)+1
        best[a[i]]=max(best[a[i]],curr[a[i]])
        rec[a[i]]=cs
print(max(best))

n, c = list(map(int, input().split()))
a = [0]
a.extend([int(i) for i in input().split()])
cntc = [0]
seg = {}
last = {}
for i in range(1, n + 1):
	cntc.append(cntc[i - 1] + (1 if a[i] == c else 0))
def getcntc(left, right):
	# [left, right]
	return cntc[right] - cntc[left - 1]
for i in range(1, n + 1):
	# print(-getcntc(last.setdefault(a[i], 0) + 1, i - 1))
	seg.setdefault(a[i], []).append(-getcntc(last.setdefault(a[i], 0) + 1, i - 1))
	last[a[i]] = i
	seg[a[i]].append(1)
for key in seg:
	# print(key, last[key])
	seg[key].append(-getcntc(last[key] + 1, n))
total = 0
m = max(a)
for d in range(1, m + 1):
	peak = 0
	ans = 0
	if d in seg and d != c:
		# print(seg[d])
		for s in seg[d]:
			ans = max(0, ans + s)
			peak = max(ans, peak)
		peak += getcntc(1, n)
	total = max(total, peak)
total = max(total, getcntc(1, n))
print(total)




import sys

line = sys.stdin.readline().strip().split()
n = int(line[0])
c = int(line[1])
a = list(map(int, sys.stdin.readline().strip().split()))
cright = [0] * (n + 1) 
maxfreq = [0] * (5 * 10 ** 5 + 1)

for i in range (0, n):
    if a[n - 1 - i] == c:
        cright[n - 1 - i] = cright[n - i] + 1
    else:
        cright[n - 1 - i] = cright[n - i]

result = cright[0]
cleft = 0

for i in range (0, n):
    if a[i] != c:
        maxfreq[a[i]] = max([maxfreq[a[i]], cleft]) + 1
    else:
        cleft = cleft + 1
    if maxfreq[a[i]] + cright[i + 1] > result:
        result = maxfreq[a[i]] + cright[i + 1]

print(result)



def __starting_point():
    length,target = [int(i) for i in input().strip().split()]
    
    array = [1000000000000]+[int(i) for i in input().strip().split()]
    num_dict = dict()
    up,down,pre,dp = [],[],dict(),[0 for i in range(length+1)]
    index = 0
    ans = 0
    for i in range(length+1):
        if array[i] == target:
            index += 1
            up.append(index)
        else:
            up.append(index)
    index = 0
    for i in range(length,-1,-1):
        if array[i] == target:
            index += 1
            down.append(index)
        else:
            down.append(index)
    down.reverse()
    down.append(0)

    for i in range(1,length+1):
        if array[i] not in pre:
            pre[array[i]] = 0
        dp[i]=max(up[i-1]+1,dp[pre[array[i]]]+1)
        pre[array[i]]=i
        #print(i)
        ans=max(ans,dp[i]+down[i+1])
    print(ans)

__starting_point()

k=[*map(int,input().split())]
list1=[*map(int,input().split())]
z= [0]*500001
o=0

for i in list1:
    z[i]=max(z[i],z[k[1]])
    z[i]+=1
    o=max(o,z[i]-z[k[1]])
print(o+z[k[1]])

k=[*map(int,input().split())]
list1=[*map(int,input().split())]
z= [0]*500001
o=0

for i in list1:
    z[i]=max(z[i],z[k[1]])
    z[i]+=1
    o=max(o,z[i]-z[k[1]])
print(o+z[k[1]])

n, c = list(map(int, input().split()))
cnt = [0] * 500005
ans = 0
for v in map(int, input().split()):
    if v == c:
        cnt[c] = cnt[c] + 1
    else:
        if cnt[v] < cnt[c]:
            cnt[v] = cnt[c]
        cnt[v] += 1
    ans = max(ans, cnt[v] - cnt[c])
print(ans + cnt[c])


def maxseg(a):
    cur_max=0
    global_max=0 
    pre_=0
    
    for i, x in enumerate(a):
        if x>0:
            cur_max=max(x, cur_max+pre_+x)
            global_max=max(global_max, cur_max)
        else:
            pre_=x  
            
    return global_max        

def push(d, u, i):
    if u not in d:
        d[u]=[]
    d[u].append(i)
    
def get_sum(a, l, r):    
    if l==0:
        return a[r]
    return a[r]-a[l-1]

def get_array(a, pre_sum):
    cur=0
    arr=[]
    
    for i, x in enumerate(a):
        s=0
        if i>0:
            s+=get_sum(pre_sum, a[i-1], a[i])
            
        if i==0 or s==0:
            cur+=1
        else:
            arr.append(cur)
            arr.append(-s)
            cur=1
    
    arr.append(cur)
    return arr        

n, c = map(int, input().split()) 
a    = list(map(int, input().split()))

d={}
pre_sum=[0]*len(a)
pre=0

for i, x in enumerate(a):
    if x==c:
        pre+=1
    else:    
        push(d, x, i)
    pre_sum[i]=pre
        
max_=0        
for pos_arr in d.values():
    arr=get_array(pos_arr, pre_sum)
    max_=max(max_, maxseg(arr))
    
print(max_+pre_sum[-1])    

line = input().split()
n = int(line[0])
c = int(line[1])
line = [int(x) for x in input().split()]

base_ans = 0
for num in line:
    if num == c:
        base_ans += 1

lut = {}
best_delta = 0
for num in line:
    if num == c:
        to_delete = []
        for key in lut:
            lut[key] -= 1
            if lut[key] <= 0:
                to_delete.append(key)
        for key in to_delete:
            del lut[key]
    else:
        if num in lut:
            lut[num] += 1
        else:
            lut[num] = 1
        
        if lut[num] >= best_delta:
            best_delta = lut[num]

print(base_ans + best_delta)