wizardrabbit   3년 전

* 본 지문은 26738번 문제를 번역한 것입니다. 의역이 있을 수 있으며, 지문을 깔끔하게 작성할 목적으로 지문의 내용을 수정하거나 재작성했을 수도 있습니다.

문제

preview

어떤 사탕 가게에는 매우 길쭉한 거대 사탕을 판매한다고 한다. 이 사탕은 $N$ 개의 작은 사탕을 일렬로 붙여서 만들어진다.

이 거대 사탕을 이루는 각각의 작은 사탕은 특정한 맛을 가지고 있다. 맛은 자연수로 나타낼 수 있다고 한다.

이 거대 사탕은 너무 크기 때문에, 당신은 거대 사탕을 적절히 쪼개 만든 사탕 조각 하나만을 구매하고자 한다. 아래와 같은 방법으로 만든 사탕을 우리는 사탕 조각이라 부른다.

  ● 거대 사탕의 왼쪽과 오른쪽에서 원하는 개수의 조각을 떼내어 버린다 ($0$ 개도 가능).

  ● 거대 사탕을 쪼갤 때에는 작은 사탕 단위로만 쪼개야 한다.

위의 방법으로 사탕 조각을 얻었을 때, 이 사탕 조각에 같은 맛의 사탕이 $3$ 개 이상 포함되어 있다면, 우리는 이 사탕 조각을 맛있는 사탕이라 부른다.

거대 사탕의 맛의 정보가 주어지면, 이 거대 사탕을 적절히 쪼개 얻을 수 있는, 가장 적은 개수의 사탕으로 이루어진 맛있는 사탕에 포함된 작은 사탕의 개수를 구하는 프로그램을 작성하시오. 맛있는 사탕을 만들 수 없는 경우도 있는데, 여러분의 프로그램은 이 경우도 판별해 주어야 한다.

입력

입력은 아래와 같이 주어진다. $A_i$ 는 거대 사탕을 이루는 $i$ 번째 사탕의 맛이다.

N
A1 A2 A3 ... AN

출력

만약 맛있는 사탕을 만들 수 있는 경우에는, 첫째 줄에 문제에서 요구한 답을 출력한다.

맛있는 사탕을 만들 수 없는 경우에는, 첫째 줄에 "NIE" 를 출력한다.

제한

$1 \le N \le 500,000$

$1 \le A_i \le 10^9$

댓글을 작성하려면 로그인해야 합니다.