Яхуб готовится к международной олимпиаде по программированию. А лучшая подготовка — это играть в Zuma-подобную игру!
В этой игре n шариков лежат в ряд. Каждый шарик окрашен в один из k цветов. Изначально в ряду нет трех или более подряд лежащих шариков одного цвета. У Яхуба есть один шар цвета x. Он может поместить свой шар в любое место ряда (даже между двумя шариками). Если в какой-то момент времени в ряду есть три или более лежащих подряд шариков одного цвета, они немедленно уничтожаются. Это правило применяется, возможно, несколько раз.
Например, если у Яхуба есть ряд шариков [черный, черный, белый, белый, черный, черный] и белый шарик, он может поместить свой шарик между двумя белыми шариками. Затем три белых шарика уничтожаются, после уничтожения белых шариков четыре черных шарика теперь лежат подряд, поэтому все они уничтожаются. В итоге ряд не будет содержать шариков, то есть Яхуб уничтожит все 6 шариков.
Яхуб хочет уничтожить как можно больше шариков. Вам дано описание ряда шариков и цвет шарика Яхуба. Помогите Яхубу подготовиться к международной олимпиаде по программированию, скажите ему, какое максимальное количество шариков из ряда он может уничтожить.