바텐더

'데이브 더 다이버'는 생태와 지형이 변하는 신비한 블루홀을 배경으로 한 하이브리드 해양 탐험 게임이다. 낮에는 아름다운 바닷속에서 탐험을 진행하고, 저녁에는 채집한 식재료로 초밥을 만들어 초밥집을 운영한다.

당신은 초밥집의 바텐더로 일하면서 손님들에게 녹차를 대접하는 일을 주로 맡고 있다.

어느 날 저녁, 당신 앞에는 $N$ 명의 손님이 녹차를 마시고 있다. 현재 $i$ 번째 손님의 컵에는 녹차가 $A_i$ 만큼 채워져 있다.

손님들은 각자의 컵에 있는 녹차의 양이 서로 다른 것을 싫어하기 때문에, 모든 손님의 컵에 있는 녹차의 양을 같게 만들고 싶다.

당신은 리드믹한 바텐더이기 때문에, $1$, $2$, $4$, $1$, $2$, $4$, $1$, $2$, $4$, $\cdots$ 의 규칙에 맞게 녹차를 추가할 수 있다. 즉, 모든 $1$ 이상인 정수 $k$에 대해, $3k - 2$ 턴에는 정확히 $1$만큼, $3k - 1$ 턴에는 정확히 $2$만큼, $3k$ 턴에는 정확히 $4$만큼 한 손님의 컵에 녹차를 추가하거나, 녹차를 추가하지 않고 턴을 넘길 수 있다. 이 문제에서 컵의 용량은 무한히 크다고 가정하자.

모든 손님의 컵에 있는 녹차의 양이 같아지도록 하는 최소 턴의 수를 계산하는 프로그램을 작성하시오.

입력 형식

첫 줄에 손님의 수 $N$이 주어진다. ($1 \le N \le 100\,000$)

두 번째 줄에 각 손님의 컵에 있는 녹차의 양을 나타내는 $N$ 개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 1\,000\,000\,000$)

출력 형식

첫 줄에 모든 손님의 컵에 있는 녹차의 양이 같아지도록 하는 최소 턴의 수를 출력한다.

예제 1

3
2 3 1

2

예제 2

4
2 3 4 1

5

예제 3

4
2 2 2 2

0

예제 설명

예제 1에서, 첫 턴에 첫 손님의 컵에 녹차를 $1$만큼 추가하고 두 번째 턴에서 세 번째 손님의 컵에 녹차를 $2$만큼 추가하면 모든 손님의 컵에 있는 녹차 양이 $3$으로 같아진다.

예제 2에서, 첫 턴에서 두 번째 손님의 컵에 녹차 $1$만큼 추가하고, 두 번째 턴에서 첫 번째 손님의 컵에 녹차 $2$만큼 추가하고, 세 번째 턴에서는 아무것도 하지 않고, 네 번째와 다섯 번째 턴에서 마지막 손님의 컵에 녹차를 $1$만큼, $2$만큼을 추가하면 모든 손님의 컵에 있는 녹차 양이 $4$로 같아진다.

예제 3에서, 처음부터 모든 손님의 컵에 있는 녹차의 양이 같으므로, 최소 턴의 수는 $0$이 된다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설