#1798 표절 검사

39  1 s   128 MB  

Description

WPC(월드 프로그래밍 클래식)의 참가자들은 총 N개의 파일의 (F1, F2, ..., FN)  소스코드를 제출했다.

채점 후 최종 결과를 발표하기 이전에, 혹시나 부정행위가 발생하지 않았는지 알아보고자 채점관들은 소스코드들의 유사성을 검사한다.

유사성 검사 프로그램은 2개의 파일의 내용을 입력 받아서 얼마나 비슷한지를 판단한다.

기본적으로 모든 소스코드에 대한 검사를 위해서는 가능한 모든 파일 쌍에 대해서 검사를 해야 할 것이다.

하지만 제출된 파일의 수가 많고, 어떤 파일의 경우에는 파일 용량의 차이가 많이 나기 때문에 굳이 비교를 할 필요가 없을 것이다.

따라서 다음과 같은 규칙을 세워서 시간을 절약하여 가급적이면 빠른 시간 내에 WPC의 결과를 발표하려고 한다.

임의의 파일 쌍 fi, fj 에 대해(단 i ≠ j) size(fi) ≤ size(fj) 이고 size(fi) ≥ 0.9 * size(fj) 일 경우에만 비교를 한다.

위의 규칙을 지킬 때 비교 하게 되는 파일 쌍의 수를 출력하는 프로그램을 작성하라.

Input

입력은 두 줄로 이뤄지며, 1이상 100,000이하의 정수 N이 입력된다. 그 다음줄에는 총 N개의 1이상 100,000,000이하의 정수가 입력되며, size(f1), size(f2), ..., size(fN)을 뜻한다.

Output

규칙을 지켰을 때 비교하게 되는 최소 횟수를 출력한다.

Sample Input

Sample Output

2
2 1
0

Sample Input 2

5
1 1 1 1 1

Sample Output 2

10