맥주 머그

Damian은 맥주 머그 수집가다. 그의 컬렉션은 빈티지한 나무 캐비닛의 선반 대부분을 차지하고 있으며, 모든 머그가 자랑스럽게 전시되어 있다. 머그는 다양한 브랜드로 이루어져 있고, 같은 브랜드의 머그가 여러 개 있는 경우도 흔하다.

Damian의 컬렉션에서 한 선반 위의 머그는 항상 하나의 대칭적인 줄을 이룬다. 줄이 대칭이라는 것은, 머그를 왼쪽에서 오른쪽으로 하나씩 감상할 때와 오른쪽에서 왼쪽으로 하나씩 감상할 때 각 머그 브랜드의 나열이 같다는 뜻이다. 캐비닛에는 아직 빈 선반이 하나 남아 있고, Damian은 그 선반을 새 머그 세트로 채울 기회를 찾고 있다.

널리 알려진 Mastodon 양조장(울리 매머드 맥주로 유명하다)은 매년 이른바 맥주 시즌을 연다. 시즌 참가자는 매일 맥주 양조 활동을 하고, 그 대가로 매일 특별한 수집용 머그를 받는다. 시즌의 각 날짜에는 특정 머그 브랜드가 배정된다. 시즌 전체 날짜의 머그 브랜드는 미리 알려져 있으며, 일부 브랜드는 시즌 중 여러 번 등장할 수 있다.

참가자는 시즌 전체에 가입할 수도 있고 일부 기간에만 가입할 수도 있다. 다만 참가하는 모든 날은 하나의 끊기지 않은 날짜 연속 구간이어야 하며, 며칠 쉬었다가 다시 돌아오는 것은 불가능하다.

Damian은 맥주 시즌에 참여하고 싶어 한다. 그는 집으로 가져올 머그 세트가 머그를 추가하거나 빼지 않고도 자신의 전시에 맞아야 하고, 그 세트가 최대한 커야 한다고 정했다.

양조장이 맥주 시즌 전체 날짜에 대해 제공한 머그 브랜드 목록이 주어질 때, 맥주 시즌의 적절히 선택한 일부 구간에 가입해서 얻을 수 있는, Damian의 전시에 맞는 가장 큰 머그 세트의 크기를 구하시오.

첫 번째 줄에는 양조장 맥주 시즌의 날짜 수를 나타내는 정수 N(1 < N ≤ 300 000)이 주어진다. 다음 줄에는 시즌에서 날마다 제공되는 모든 맥주 머그 브랜드의 목록을 나타내는 N개의 문자가 주어진다. 목록은 시즌 첫날부터 마지막 날까지 자연스러운 순서로 되어 있다. 각 브랜드는 'a'부터 't'까지의 소문자 하나로 표현된다. 목록에는 공백이 없다.

Damian이 양조장 맥주 시즌에서 가져올 수 있고, 변경 없이 자신의 컬렉션 전시에 맞는 가장 큰 머그 세트의 크기를 나타내는 정수 하나를 출력한다.