시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 267 93 78 45.614%

문제

구슬을 엄청 좋아하는 비드맨이 있다. 구슬만 보면 갖고 싶어 하는 비드맨은 오늘도 갖고 싶은 구슬을 발견했다. 그러나 비드맨은 현재 구슬을 너무 많이 갖고 있기 때문에 더 이상 구슬을 가질 수 없는 지경에 이르렀다.

비드맨은 서로 다른 종류의 구슬 두 개를 부딪히면 서로 깨져 없어진다는 것을 알고 있다. 이 사실을 이용해서 비드맨은 현재 가지고 있는 구슬의 개수를 최소로 하고자 한다. 그러나 구슬의 개수가 많기 때문에 비드맨은 도저히 계산을 할 수가 없었다.

길거리 해결사인 당신은 길거리에서 고민에 빠진 비드맨을 발견했고, 비드맨에게 고민에 빠진 이유를 듣게 된다. 인연인 만큼 당신은 비드맨의 고민을 해결해주려고 한다. 서로 다른 종류의 구슬 두 개를 부딪혀서 최대한 구슬을 없앤다고 할 때 남게 되는 구슬의 개수는 몇 개인지를 구하면 된다.

입력

첫 번째 줄에는 비드맨이 가지고 있는 구슬의 종류 N이 주어진다. (1 ≤ N ≤ 105)

두 번째 줄부터 N개의 줄에는 x1, x2​, x3, ..., xN이 주어진다. xi는 비드맨이 가지고 있는 i번째 종류의 구슬의 개수이다. (1 ≤ xi ≤ 109)

출력

비드맨이 최대한 많이 구슬을 없앴을 때 남는 구슬의 개수를 출력한다.

예제 입력 1

1
1000000000

예제 출력 1

1000000000

예제 입력 2

2
100
50

예제 출력 2

50

예제 입력 3

3
2
2
4

예제 출력 3

0