사과 배달

사과 농부 잉그리드는 자신과 이웃들에게 나누어 주려고 엄청난 양의 사과를 방금 수확했다. 그녀의 동네는 정수 좌표를 갖는 모든 점에 정확히 하나의 집이 있는 무한 평면으로 나타낼 수 있다. 잉그리드의 집은 원점 $(0, 0)$에 있다. 잉그리드는 사과를 나누어 줄 때 특별한 전략을 사용한다. 먼저 음이 아닌 정수들의 목록 $r_1, r_2, \cdots, r_N$을 선택한다. 그런 다음 목록의 각 수에 대해 반지름 $r_i$ 이내에 있는 모든 집, 즉 좌표가 $x^2+y^2 \leq r_i^2$을 만족하는 모든 집에 사과를 하나씩 준다 (자신의 집도 포함한다). 이 방법을 사용하면 잉그리드와 가까운 이웃들은 먼 이웃들보다 더 많은 사과를 받는다.

잉그리드는 방금 반지름 목록을 골랐지만, 문제가 생겼다. 사과를 나누어 줄 때 그녀는 항상 상자마다 사과가 여덟 개씩 들어가는 정육면체 모양의 상자에 사과를 담는다. 따라서 나누어 주는 사과의 총개수가 여덟의 배수인 것이 매우 중요하다. 잉그리드는 나누어 주는 사과의 개수가 여덟의 배수가 되도록 목록에서 일부 반지름을 제거해야 한다. 예를 들어 모든 반지름을 제거하면 되므로, 이렇게 하는 것은 항상 가능하다. 하지만 잉그리드는 욕심쟁이로 보이고 싶지 않기 때문에, 원래 나누어 주려고 계획했던 사과 중 나누어 주지 않는 사과의 개수가 최소가 되도록 반지름을 제거하려 한다. 이 최솟값을 구하는 것이 여러분의 과제다.

채점

여러 테스트 그룹으로 여러분의 풀이를 테스트한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$15$| 모든 $i$에 대해 $N \leq 10$, $r_i \leq 300$

$2$ |$25$| 모든 $i$에 대해 $N \leq 3000$, $r_i \leq 1000$

$3$ |$15$| 모든 $i$에 대해 $r_i \leq 10^4$

$4$ |$45$| 추가 제한 없음.

입력의 첫 번째 행에는 반지름의 개수를 나타내는 정수 $N$ ($1 \leq N \leq 3 \cdot 10^5$)이 주어진다.

다음 줄에는 선택한 반지름을 나타내는 공백으로 구분된 정수 $N$개 $r_1, r_2, \cdots, r_N$ ($0 \leq r_i \leq 3 \cdot 10^5$)가 주어진다.

목록에서 반지름을 제거하여 나누어 주는 사과의 총개수가 여덟의 배수가 되게 할 때, 잉그리드가 나누어 주지 않을 수 있는 사과 개수의 최솟값을 정수로 출력한다.

반지름이 다음과 같을 때: 0에는 집이 1채 있고, 1에는 집이 5채 있으며, 2에는 집이 13채 있다. 따라서 해당 반지름들 이내에는 총 26채의 집이 있다. 두 반지름 0을 제거하면 24채의 집이 남는다.