33047번 - 순정$N$련보등

문제

preview

구련보등^九蓮寶燈은 마작의 역 중 하나로 ‘9ドル$개의 연꽃 보배 등잔’이라는 뜻을 가지고 있습니다.

구련보등의 형태 중 하나인 순정구련보등^{純正九蓮寶燈}은 한 종류의 수패로 1ドル$과 9ドル$를 각각 3ドル$장씩, 2ドル$부터 8ドル$을 각각 1ドル$장씩 손에 가지고 있는 상태에서 같은 종류의 수패 1ドル$부터 9ドル$ 사이의 아무 패를 한 장 더 가져와 완성하면 되는 역입니다. 이렇게 손에 1ドル$과 9ドル$가 각각 3ドル$장씩, 2ドル$부터 8ドル$이 각각 1ドル$장씩 있어 남은 한 장을 더 가져오면 완성할 수 있는 상태를 ‘순정구련보등 텐파이’라고 하는데, 이 때 패를 비내림차순으로 정리하면 다음과 같은 형태가 됩니다.

1112345678999

개척단 훈련소 마장에서 플레이하는 ‘순정$N$련보등 마작’은 수패 중에서도 만수패만 사용하며 1ドル$부터 $N$까지 총 $N$종류의 만수패가 존재합니다. 순정$N$련보등 마작에서의 ‘순정$N$련보등 텐파이’는 1ドル$이 3ドル$장, 2,ドル\dots ,N-1$이 한 장씩, $N$이 3ドル$장이 연속되게 $N+4$장 있는 형태를 말합니다. 이때, 패에 적혀 있는 수는 반드시 비내림차순이 되어야 합니다.

여러분은 바닥에 일렬로 놓여진 $K$장의 패를 확인하다가 패를 적절히 교체하여 순서대로 정리된 순정$N$련보등 텐파이 형태가 있도록 만들 수 있는지 궁금해졌습니다.

패를 교체하는 것은 어려운 일입니다. 따라서 패를 교체할 때는 한 장의 패를 골라 해당 패에 적힌 수와 1ドル$ 차이가 나는 인접한 수가 적힌 패로만 교체할 수 있고, 1ドル$보다 작거나 $N$보다 큰 수의 패로는 교체할 수 없습니다. 같은 위치의 패를 여러 번 교체하는 것은 허용됩니다.

바닥에 놓여진 패들이 주어졌을 때, 하나 이상의 길이 $N+4$의 구간이 순정구련보등 텐파이 형태가 되기 위해 필요한 최소 교체 횟수를 구해 주세요.

입력

첫 번째 줄에 마작패의 종류 수 $N$과 바닥에 놓여진 패의 개수 $K$가 공백으로 구분되어 주어집니다. $(3 \le N \le 399,996円;$ $N \equiv 0 \pmod{3};$ $N+4 \le K \le 400,000円)$

두 번째 줄에 바닥에 놓여진 패의 종류를 나타내는 $K$개의 정수 $A_1, \dots, A_K$가 공백으로 구분되어 주어집니다. $i$번째 수는 $i$번째로 놓여 있는 패에 적혀 있는 수입니다. $(1 \le A_i \le N)$

출력

하나 이상의 구간을 순정$N$련보등 텐파이 형태로 만들기 위한 최소 교체 횟수를 출력합니다.

하나도 교체하지 않아도 순정$N$련보등 텐파이 형태가 존재한다면 0을 출력합니다.

제한

힌트