Iahub is training for the IOI. What is a better way to train than playing a Zuma-like game? 

There are n balls put in a row. Each ball is colored in one of k colors. Initially the row doesn't contain three or more contiguous balls with the same color. Iahub has a single ball of color x. He can insert his ball at any position in the row (probably, between two other balls). If at any moment there are three or more contiguous balls of the same color in the row, they are destroyed immediately. This rule is applied multiple times, until there are no more sets of 3 or more contiguous balls of the same color. 

For example, if Iahub has the row of balls [black, black, white, white, black, black] and a white ball, he can insert the ball between two white balls. Thus three white balls are destroyed, and then four black balls become contiguous, so all four balls are destroyed. The row will not contain any ball in the end, so Iahub can destroy all 6 balls.

Iahub wants to destroy as many balls as possible. You are given the description of the row of balls, and the color of Iahub's ball. Help Iahub train for the IOI by telling him the maximum number of balls from the row he can destroy.


-----Input-----

The first line of input contains three integers: n (1 ≤ n ≤ 100), k (1 ≤ k ≤ 100) and x (1 ≤ x ≤ k). The next line contains n space-separated integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ k). Number c_{i} means that the i-th ball in the row has color c_{i}.

It is guaranteed that the initial row of balls will never contain three or more contiguous balls of the same color. 


-----Output-----

Print a single integer — the maximum number of balls Iahub can destroy.


-----Examples-----
Input
6 2 2
1 1 2 2 1 1

Output
6

Input
1 1 1
1

Output
0

Difficulty: interview

Starter code:

Solutions:
import copy

n, k, x = map(int, input().split())
c = list(map(int, input().split()))
for i in range(n):
    c[i] = (c[i],0)
ans = 0
for i in range(n + 1):
    c2 = copy.deepcopy(c)
    c2.insert(i, (x,1))
    while True:
        dq = False
        for i in range(len(c2) - 2):
            if c2[i][0] == c2[i + 1][0] == c2[i + 2][0]:
                le = i
                re = i
                while re < len(c2) and c2[re][0] == c2[le][0]:
                    re += 1
                c2 = c2[:le] + c2[re:]
                dq = True
                break
        if not dq:
            break
    cntdel = 0
    for a,b in c2:
        if b==0:
            cntdel+=1
    ans = max(ans, n - cntdel)
print(ans)

(n, k, x) = input().split()
n, k = int(n), int(k)
balls = input().split()
ans = 0

for i in range(n):
    s = balls.copy()
    s.insert(i, x)
    while len(s) > 2:
        l = len(s)
        for j in range(2, len(s)):
            if s[j-2] == s[j-1] == s[j]:
                p = j + 1
                while p < len(s):
                    if s[j] != s[p]:
                        break
                    p += 1
                s = s[:j-2] + s[p:]
                break
        if len(s) == l:
            break
    ans = max(ans, n - len(s))

print(ans)


n, k, x = list(map(int, input().split()))
def lr_bound(c, i, x):
    l = i
    r = i

    while l > 0 and c[l - 1] == x:
        l -= 1
    while r < len(c) - 1 and c[r + 1] == x:
        r += 1
    return l, r
def destroy(c, i, x):
    c = c[:]
    c.insert(i, x)
    
    dest = 0
    while len(c) > 2:
        if i >= len(c):
            i = len(c) - 1
        if i < 0:
             i = 0
        l, r = lr_bound(c, i, c[i])
        if r - l >= 2:
            c[l:r+1] = []
            dest += (r - l) + 1
            i = l
        else:
            break
    return dest - 1


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

scores = []
for i in range(len(c)):
    scores.append(destroy(c, i, x))

print(max([0] + scores))


def can_destroy(A):
    color_now = A[0]
    num_now = 1
    for i in range(1, len(A)):
        if color_now == A[i]:
            num_now += 1
            if num_now == 3:
                return i - 2
        else:
            color_now = A[i]
            num_now = 1
    return -1
        

def destroy(A):
    while len(A) > 0 and can_destroy(A) != -1:
        i = can_destroy(A)
        c = A[i]
        while i < len(A) and A[i] == c:
            A.pop(i)
    return A

n, k, x = map(int, input().split())
A = list(map(int, input().split()))
res = 0
for i in range(len(A) + 1):
    B = A[:]
    B.insert(i, x)
    B = destroy(B)[:]
    res = max(res, len(A) - len(B))
print(res)

n, k, x = list(map(int, input().split()))

s = list(map(int, input().split()))

def fl(x, e, c):
    s = x[:e]
    s.append(c)
    s += x[e:]
    for j in range(55):
        for i in range(len(s)-2):
            if s[i] == s[i+1] == s[i+2]:
                if i < len(s)-3:
                    if s[i] == s[i+3]:
                        del s[i]
                del s[i]
                del s[i]
                del s[i]
                break

    return len(s)


m = 0

for i in range(n):
    m = max(m, n - fl(s,i,x))

print(m)


import sys
import math
import random
n, k, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
if n == 1:
    print(0)
    return
for i in range(0, n - 1):   
    if a[i] == a[i + 1] == x:
        l = i    
        while l >= 0 and a[i] == a[l]:
            l -= 1
        r = i + 1
        while r < n and a[r] == x:
            r += 1
        while (1):
            if l == -1 or r == n:
                break
            if a[l] != a[r]:
                break
            if l == 0 and r == n - 1:
                break
            if l == 0:
                if a[0] == a[r + 1]:
                    while r < n and a[r] == a[0]:
                        r += 1
                    l -= 1
                    continue
                else:
                    break
            if r == n - 1:
                if a[n - 1] == a[l - 1]:
                    while l >= 0 and a[l] == a[n - 1]:
                        l -= 1
                    r += 1
                    continue
                else:
                    break
            if a[l] == a[r + 1] or a[l - 1] == a[r]:
                t = a[l]
                while l >= 0 and a[l] == t:
                    l -= 1
                while r < n and a[r] == t:
                    r += 1
            else:
                break
        ans = max(ans, r - l - 1)     
print(ans)

n,k,x = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]

m = 0

def scan(l,m):
    if len(l) == 0:
        return l,m
    mstart = 0
    mle = 1
    start = 0
    col = l[0]
    le = 1
    for i in range(1,len(l)):
        if l[i] == col:
            le += 1
        else:
            if le > mle:
                mle = le
                mstart = start
            col = l[i]
            start = i
            le = 1
    if le > mle:
        mle = le
        mstart = start
    if mle < 3:
        return l,m
    #print(mle,mstart,l)
    m += mle
    l = l[:mstart] + l[mstart+mle:]
    #print(l)
    return l,m

for i in range(len(l)+1):
    l2 = l[:]
    m2 = -1
    l2 = l2[:i] + [x] + l2[i:]
    
    while True:
        l2, m3 = scan(l2, m2)
        if m2 == m3:
            break
        m2 = m3
    #print(m2)
    #print()
    m = max(m,m2)
print(m)


def check(start):
    nonlocal groups
    cnt = 2
    d = 1
    while d <= min(start, len(groups) - start - 1):
        if groups[start - d][0] == groups[start + d][0]:
            if groups[start - d][1] + groups[start + d][1] >= 3:
                cnt += groups[start - d][1] + groups[start + d][1]
                d += 1
                continue
        return cnt
    return cnt

n, k, x = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
groups = []
i = 0
while i < n - 1:
    if c[i] == c[i + 1]:
        groups.append([c[i], 2])
        i += 2
    else:
        groups.append([c[i], 1])
        i += 1
if n == 1 or c[-1] != c[-2]:
    groups.append([c[-1], 1])
res = 0
for i in range(len(groups)):
    if groups[i][0] == x and groups[i][1] == 2:
        res = max(res, check(i))
print(res)

n, k, x = list(map(int,input().split()))
c0 = list(map(int,input().split()))
max = 0
for i in range (len(c0)-1):
    c = c0[:]
    s = 0
    if c[i]==c[i+1]==x:
        del c[i:i+2]
        s += 2
        possib = True
        while possib:
            if i>0 and i<len(c):
                if 1<i<len(c)-1 and c[i-2]==c[i-1]==c[i]==c[i+1]:
                    del c[i-2:i+2]
                    s += 4
                    i -= 2
                elif 1<i and c[i-2]==c[i-1]==c[i]:
                    del c[i-2:i+1]
                    s += 3
                    i -= 2
                elif i<len(c)-1 and c[i-1]==c[i]==c[i+1]:
                    del c[i-1:i+2]
                    s += 3
                    i -= 1
                else:
                    possib = False
            else:
                possib = False
    if s > max:
        max = s
print(max)
                


def busted_balls(balls,idx):
    #print(idx)
    busted=2
    i=idx-1
    j=idx+2
    while(i>=0 and j < len(balls) and balls[i] == balls[j]):
        while(i-1 >= 0 and balls[i] == balls[i-1]):
            i-=1
        while j+1 < len(balls) and balls[j] == balls[j+1]:
            j+=1
        #print('i'+str(i))
        #print('j'+str(j))
        if j-i+1-busted>=3:
            busted=(j-i+1)
        else:
            break
        #print(busted)
        i-=1
        j+=1
        #print('i'+str(i))
        #print('j'+str(j))
    return busted

n,k,x=list(map(int,input().split()))
balls=list(map(int,input().split()))
best=0
for i in range(1,n):
    if balls[i]==balls[i-1] and balls[i]==x:
        #copy_balls=balls[:]
        #copy_balls.insert(i)
        res = busted_balls(balls,i-1)
        if(res>best):
            best=res
print(best)




import sys

f = sys.stdin
#f = open('H:\\Portable Python 3.2.5.1\\tests\\test_445B1.txt')
n, k, x, = list(map(int, f.readline().split()))

r = [int(it) for it in  f.readline().split()]


#print(n, k, x)

#print(r)


def collaps(r,k):
    n = len(r)
    max_collaps = 0
    if n<k:
        return 0
    elif n==1 and k==1:
        return 1
    elif n==1 and k>1:
        return 0
    else:
        i = 1
        g = 1
        col = r[0]
        while (i<n):
            if r[i]==col:
                g += 1
            else:
                if g>=k:
                    max_collaps += g
                    col = r[i]
                    for kk in range(g):
                        # print(i-1, r)
                        del r[i-1]
                        i -= 1
                    n = len(r)
                    if n>1:
                        g = 1
                        i = 1
                        col = r[0]
                        continue
                    else: break
                else:
                    g = 1
                    col = r[i]
            #print(i, r, r[i],col, g, max_collaps)        
            i += 1
            
        if g>=k:
            max_collaps += g
        #print(6575, i, g, max_collaps)    
        return max_collaps

r1 = r[:]


nn = 0 # Новый ряд
res = 0
c1 = 0
for m in range(len(r)) :
    if (nn == 0) and (r[m]==x):
        r1 = r[:]
        r1.insert(m,x)
        c1 = collaps(r1,3)-1
        #print(m, c1)
        if  c1>res:     res = c1
        nn = 1
    elif (r[m]!=x):
        nn = 0
    # print(m, nn, c1, res)        
    
print(res)


n, k, x = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
for i in range(n+1):
    b = a[:i] + [x] + a[i:]+[-1]
    for j in range(123):
        #print(b)
        c = 1
        for j in range(1, len(b)):
            #print(j)
            if b[j] == b[j - 1]:
                c += 1
            else:
                if c >= 3:
                    b = b[:(j - c)] + b[j:]
                    break
                c = 1
    #print(b)
    #print()
    ans = max(len(a) - len(b) + 1, ans)
print(ans)

n,k,x,=list(map(int,input().split()))

L=list(map(int,input().split()))

ans=0
for i in range(n):
    X=list(L[0:i])+[x]+list(L[i:])
    a=0
    while(1):
        cont=False
        cnt=1
        z=0
        for i in range(1,len(X)):
            if(X[i]==X[i-1]):
                cnt+=1
            else:
                if(cnt>=3):
                    X=list(X[0:z])+list(X[i:])
                    cont=True
                    break
                else:
                    cnt=1
                    z=i
        if(cont):
            continue
        if(cnt>=3):
            X=list(X[:z])
            continue
        break
    ans=max(ans,n-len(X))
print(ans)


from itertools import *
R = lambda: map(int, input().split())
n, k, x = R()
c = [(k, len(list(g))) for k, g in groupby(R())]
count = 0
for i in range(len(c)):
  if c[i][0] == x and c[i][1] > 1:
    a = c[i][1]
    l, r = i - 1, i + 1
    while l >= 0 and r < len(c) and c[l][0] == c[r][0] and c[l][1] + c[r][1] > 2:
      a += c[l][1] + c[r][1]
      l -= 1
      r += 1
    count = max(count, a)
print(count)

n, k, x = input().split()
t = input().split() + ['a', 'b']
u, q = -2, 1
for v in range(int(n) + 1):
    if x == t[v]:
        if u == -2: u = v - 1
    elif u != -2:
        s, i, j, y = 0, u, v, t[v]
        while j - i - s > 2:
            s = j - i
            while t[i] == y: i -= 1
            while t[j] == y: j += 1
            y = t[j]
        u, q = -2, max(q, s)
print(q - 1)

n, k, x = map(int, input().split())
colors = list(map(int, input().split()))

groups = []

i = 0
while i < n:
	c = colors[i]
	nbC = 0
	while i < n and colors[i] == c:
		i += 1
		nbC += 1
	groups.append((c, nbC))

maxNbBallsDestroyed = 0
for i, group in enumerate(groups):
	if group[0] == x and group[1] >= 2:
		nbBallsDestroyed = group[1]
		past = i-1
		future = i+1
		while past >= 0 and future < len(groups) and groups[past][0] == groups[future][0] and groups[past][1] + groups[future][1] >= 3:
			nbBallsDestroyed += groups[past][1] + groups[future][1]
			past -= 1
			future += 1
		maxNbBallsDestroyed = max(maxNbBallsDestroyed, nbBallsDestroyed)

print(maxNbBallsDestroyed)

from itertools import groupby

def destroy(chain):
	remaining = []
	for k, v in groupby(chain):
		L = list(v)
		if len(L) < 3:
			remaining.extend(L)
	if len(chain) == len(remaining):
		return len(remaining)
	else:
		return destroy(remaining)

def solve():
	n, k, x = list(map(int, input().split()))
	balls = list(map(int, input().split()))
	res = 0
	for i in range(n):
		tmp = balls[:]
		tmp.insert(i, x)
		res = max(res, n-destroy(tmp))
	return res

def __starting_point():
	print(solve())

__starting_point()

R = lambda: list(map(int, input().split()))


def dfs(a):
    cnt = 0
    n = len(a)
    a.append(10000000)
    for i in range(1, n):
        if a[i] != a[i - 1]:
            cnt = 0
        else:
            cnt += 1
        if cnt >= 2:
            j = i
            while a[j] == a[i]:
                j += 1

            return j - i + 2 + dfs(a[:i - 2] + a[j:n])
    return 0


n, k, x = R()
a = R()
ans=1
for i in range(n+1):
    ans=max(ans, dfs(a[:i]+[x]+a[i:]))

print(ans-1)

def do(l,r):
    li = 0
    ri = 0
    nl = len(l)
    nr = len(r)
    l.append(-1)
    r.append(-1)
    x = 0
    while l[li] > 0 and r[ri]>0:
        a = 0
        c = l[li]
        while l[li] == c:
            a += 1
            li += 1
        while r[ri] == c:
            a += 1
            ri += 1
        if a < 3:
            return li+ri-a-x
        x = 1
    return li+ri-x
def s():
    [n,k,x] = list(map(int,input().split()))
    c = list(map(int,input().split()))
    res = 0
    for i in range(n):
        l = [x]
        l.extend(list(reversed(c[:i])))
        res = max(do(l,c[i:]),res)
    print(res)
s()


(n, k, x) = input().split()
n, k = int(n), int(k)
balls = input().split()
ans = 0

for i in range(n):
    s = balls.copy()
    s.insert(i, x)
    while len(s) > 2:
        l = len(s)
        for j in range(2, len(s)):
            if s[j - 2] == s[j - 1] == s[j]:
                p = j + 1
                while p < len(s):
                    if s[j] != s[p]:
                        break
                    p += 1
                s = s[:j-2] + s[p:]
                break
        if len(s) == l:
            break
    ans = max(ans, n - len(s))

print(ans)


(n, k, x) = input().split()
n, k = int(n), int(k)
balls = input().split()
ans = 0

for i in range(n):
    s = balls.copy()
    s.insert(i, x)
    while len(s) > 2:
        l = len(s)
        for j in range(2, len(s)):
            if s[j-2] == s[j-1] == s[j]:
                p = j + 1
                while p < len(s):
                    if s[j] != s[p]:
                        break
                    p += 1
                s = s[:j-2] + s[p:]
                break
        if len(s) == l:
            break
    ans = max(ans, n - len(s))

print(ans)

(n, k, x) = input().split()
n, k = int(n), int(k)
balls = input().split()
ans = 0

for i in range(n):
    s = balls.copy()
    s.insert(i, x)
    while len(s) > 2:
        l = len(s)
        for j in range(2, len(s)):
            if s[j-2] == s[j-1] == s[j]:
                p = j + 1
                while p < len(s):
                    if s[j] != s[p]:
                        break
                    p += 1
                s = s[:j-2] + s[p:]
                break
        if len(s) == l:
            break
    ans = max(ans, n - len(s))

print(ans)



import re
import inspect
from copy import copy
from sys import argv, exit

def rstr():
    return input()

def rint():
    return int(input())

def rints(splitchar=' '):
    return [int(i) for i in input().split(splitchar)]

def varnames(obj, namespace=globals()):
    return [name for name in namespace if namespace[name] is obj]

def pvar(var, override=False):
    prnt(varnames(var), var)

def prnt(*args, override=False):
    if '-v' in argv or override:
        print(*args)

def remove_split(l, i, j):
    prnt("Removed {} thru {}, {}".format(i, j, l[i:j]))
    new_l = l[:i] + l[j:]
    prnt("New List: {}".format(new_l))
    return new_l

def degrade(l, initial_size):
    i=0
    color = 0
    removed = False
    for j,x in enumerate(l):
        if not color:
            color = x
            i = j
        
        if color != x:
            if j-i >= 3:
                l = remove_split(l, i, j)
                removed = True
            color = x
            i = j
        if j == len(l)-1 and color == x and j-i >= 2:
            prnt('removing {} {}'.format(i, j))
            l = remove_split(l, i, j+1)
            removed = True

    if removed:
        prnt(l)
        return degrade(l, initial_size)
    else:
        return initial_size - len(l)


def __starting_point():
    (num, kolors, xolor) = rints()
    balls = rints()
    
    results = []
    for i in range(len(balls)):
        l = copy(balls)
        l.insert(i, xolor)
        pvar(l)
        results.append(degrade(l, len(l)-1))
    prnt(results)
    ans = max(results)
    if ans == -1:
        ans = 0
    print(ans)

__starting_point()

(n, k, x) = map(int, input().split())

balls = list(map(int, input().split()))

c = 0
p = None
pairs = []
matches = []
for b in range(len(balls)):
    if(balls[b] is not c):
        c = balls[b]
    if(c is p):
        pairs.append((b - 1, b))
        if(c is x):
            matches.append((b-1, b))
    p = c

max = 0

for m in matches:
    i, j = m
    removed = 2
    i -= 1
    j += 1
    while(i >= 0 and j < len(balls)):
        if(balls[i] is balls[j]):
            toRemove = 0
            if(j < len(balls)-1 and balls[j+1] is balls[j]):
                toRemove += 1
                j+=1
            if(i >= 1 and balls[i-1] is balls[i]):
                toRemove += 1
                i-=1
            if(toRemove > 0):
                removed += toRemove + 2
            else:
                break
        else:
            break
        i -= 1
        j += 1
    if(removed > max):
        max = removed
            

print(max)