25389번 - 대충 카드로 몬스터 잡는 게임

세계적인 게임 회사 KDH Corp.에서 개발한 턴제 어드벤처 카드 게임인 『대충 카드로 몬스터 잡는 게임』이 드디어 오늘 출시되었다! 다음은 게임의 규칙을 설명한 룰북이다.

• 플레이어는 처음에 $1$번부터 $K$번까지의 카드를 각각 한 장씩 손에 들고 게임을 시작한다.
• 게임은 총 $N$개의 턴으로 구성되어 있으며, 각 턴에는 $1$번부터 $K$번까지의 몬스터 중 최대 한 마리가 등장한다.
• 플레이어는 각 턴에 손에 들고 있는 카드 중 최대 2장의 카드를 낼 수 있다. 카드를 한 장도 내지 않고 턴을 넘기는 것도 가능하다.
• 몬스터가 등장한 턴에 플레이어가 등장한 몬스터의 번호와 동일한 번호의 카드를 내면 해당 카드로 몬스터를 처치할 수 있다.
• 만약 어떤 턴에 등장한 몬스터를 그 턴에 처치하지 못하면, 몬스터는 그 턴이 끝난 뒤 도망친다.
• 플레이어가 손에 들고 있는 카드를 모두 소진하고 나면, 턴이 끝난 뒤에 $1$번부터 $K$번까지의 카드를 한 장씩 다시 손으로 들고 온다.
• 더 많은 몬스터를 처치할수록 더 높은 점수를 획득한다.

재야의 게임 고수인 도훈이는 『대충 카드로 몬스터 잡는 게임』이 출시되자마자 $1$등을 차지했지만, 그의 라이벌 강민이가 그의 $1$등 자리를 위협하고 있다! 조바심이 난 도훈이는 아예 가능한 최대 점수를 먼저 기록해서 $1$등을 뺏기는 일을 막고자 한다. 도훈이가 더욱 확실히 $1$등을 차지할 수 있도록 각 게임에서 처치할 수 있는 최대 몬스터 수를 구해주자.

첫 번째 줄에 게임의 총 턴수 $N$과 카드 및 몬스터의 종류 $K$가 공백으로 구분되어 주어진다. $(1\leq N,K\leq 500\, 000)$

두 번째 줄에 각 턴에 등장하는 몬스터의 종류 $c_1,c_2,\cdots ,c_N$이 공백으로 구분되어 주어진다. $(0\leq c_i\leq K)$ $c_i=0$이면 턴 $i$에는 몬스터가 등장하지 않았다는 뜻이다.

처치할 수 있는 몬스터 수의 최댓값을 출력한다.