해쉬(Hash)

HASH

Contents

N개의 숫자들을 개방주소 방식을 사용하는 다음의 해시 함수 h_i(x)를 이용하여 크기 M인 해시테이블에 저장한다.

h_i(x) = (x + i) % M 

해시테이블의 크기 M은 2*N보다 크거나 같은 소수 (prime number) 중 가장 작은 숫자로 한다. 예를들어, N = 5인 경우 M = 11이 된다.

이때, 숫자 N개를 해시테이블에 저장할 때 충돌이 일어나는 총 횟수를 출력한다.

Input

입력의 첫줄에는 해시테이블에 넣을 숫자의 개수 N이 들어온다.

다음 줄에 N개의 숫자가 입력된다.

Output

해시 테이블에 숫자를 입력할 때 발생하는 전체 충돌 횟수를 출력한다.

Sample Input

10

1 2 3 4 5 5 6 7 8 9

Sample Output

5