단백질 식별

단백질은 아미노산이 연결된 사슬이다. 그 서열은 이중 질량 분석(MS2)으로 알아낼 수 있다.

이 문제에서는 다음과 같이 단순화한 상황을 가정한다.

• 단백질은 최대 $400$개의 아미노산이 연결된 사슬이다.
• 아미노산은 $P$와 $Q$ 두 종류만 있다.
• $P$의 질량은 $97.05276$ 돌턴, $Q$의 질량은 $128.05858$ 돌턴이다.

MS2 실험의 결과는 실수의 집합이며, 각 실수를 피크라고 부른다. 실제 단백질의 경우, 이 집합에는 단백질의 모든 prefix와 모든 suffix의 질량(단백질 전체의 질량 포함)이 들어 있으며, 그 밖의 값은 들어 있지 않다. 어떤 단백질과 그 단백질을 뒤집은 것은 정확히 같은 prefix·suffix 질량 집합을 만든다는 점에 유의하라.

알 수 없는 단백질에 대한 실험은 완벽하지 않으므로, 그 결과는 다음을 만족한다.

• 일부 prefix 또는 suffix 질량은 집합에서 빠져 있을 수 있다.
• 집합에는 단백질의 어떤 prefix나 suffix 질량에도 해당하지 않는 피크가 들어 있을 수 있다. 이러한 피크를 노이즈 피크라고 부른다.
• 모든 피크는 양수이다.
• 가장 큰 피크는 단백질 전체의 질량과 같다.
• prefix 또는 suffix 질량에 해당하는 피크는 정확한 값이다.

실험 결과가 주어졌을 때, 전체 질량이 가장 큰 피크와 같은, $P$와 $Q$로 이루어진(길이는 최대 $400$) 모든 단백질을 생각하자. 그러한 단백질에 대해, 노이즈 피크란 그 단백질의 어떤 prefix·suffix 질량과도 같지 않은 입력 피크를 말한다. 노이즈 피크 수의 최솟값을 구하라.

첫째 줄에 피크의 수 $n$이 주어진다. ($1 \le n \le 100000$)

다음 $n$개의 줄에 각각 하나의 피크 $p_i$가 주어진다.

입력은 항상 위의 모든 조건을 만족하며, 모든 피크는 서로 다르다. 각 피크는 소수점 아래 최대 $5$자리까지 주어진다.

전체 질량이 가장 큰 피크와 같은, $P$와 $Q$로 이루어진(길이는 최대 $400$) 모든 단백질에 대해, 노이즈 피크 수의 최솟값을 정수 하나로 출력한다.