종휘는 새로운 수학 수업을 시작했다! 당신은 $N$ 개의 자연수가 들어있는 가방을 가지고 있다. 당신은 다음과 같은 작업을 마음껏 수행할 수 있다 (아예 수행 안 해도 됨):

• 가방에 들어있는 자연수 $x$, $y$ ($x > y)$ 를 골라서 꺼낸다.
• 만약 가방에 $x - y$ 의 값이 없다면, $x - y$ 의 값을 가방에 집어넣는다.

종휘는 가방에 들어있는 숫자가 가장 많은 사람에게 매점 1회 취식권을 제공하기로 하였다. 따라서 당신은 가방에 들어있는 숫자의 개수를 최대한 많게 만들어야 한다.

당신이 최대로 만들 수 있는 숫자의 개수를 구해야 한다.

입력

첫 번째 줄에 $N$ 이 주어진다. $(2 \le N \le 100,000)$

다음 줄에 $N$ 개의 자연수가 주어진다: 가방 안에 초기적으로 들어있는 숫자들이다. (주어지는 자연수는 $10^9$ 를 넘지 않는다.)

하지만 $N$ 의 크기가 $100,000$ 일 경우 테스트 케이스의 크기가 30MB 가 돼서 구름에 안 올라간다. 따라서 $N$ 이 매우 큰 경우는 없으며, 가장 테스트 케이스가 큰 경우는 $N = 10,000$ 이다.

출력

첫 번째 줄에 최대로 만들 수 있는 숫자의 개수를 출력해야 한다.

예시