题目描述

题目译自 NordicOI 2020 T1 「Apple Delivery」

Ingrid 刚刚收获了大量的苹果，她打算把这些苹果分发给自己和邻居们。她的邻居分布在一个无限大平面上，每个整数坐标点上都有一栋房子。Ingrid 的房子位于原点 $(0, 0)$。Ingrid 有一个特殊的分苹果策略。首先，她选择一组非负整数 $r_1, r_2, \cdots, r_N$。对于列表中的每个数字，她会给半径为 $r_i$ 内的每栋房子分发一个苹果，即每个满足 $x^2 + y^2 \leq r_i^2$ 的房子（包括她自己的房子）。这样，离她近的邻居会比远的邻居得到更多的苹果。

Ingrid 刚刚选好了半径列表，但出现了一个问题。她在分发苹果时总是把苹果装在每箱八个的立方体盒子里。因此，确保分发的苹果总数是八的倍数非常重要。Ingrid 需要从列表中删除一些半径，使得分发的苹果总数成为八的倍数。虽然可以通过删除所有半径来实现，但 Ingrid 不想显得太贪心，所以她希望以最小化未分发的苹果数量的方式删除半径。你的任务是找到这个最小值。

输入格式

第一行输入包含一个整数 $N$ $(1 \leq N \leq 3 \cdot 10^5)$，表示半径的数量。

接下来一行包含 $N$ 个用空格分隔的整数 $r_1, r_2, \cdots, r_N$，表示选定的半径。

输出格式

输出一个整数，表示 Ingrid 通过从列表中删除半径而不分发的最小苹果数量，使得分发的苹果总数成为八的倍数。

6
1 0 2 1 0 0

2

在半径为 $0$ 的范围内有 $1$ 栋房子，半径为 $1$ 的范围内有 $5$ 栋房子，半径为 $2$ 的范围内有 $13$ 栋房子。因此，总共有 $26$ 栋房子在这些半径范围内。通过删除两个半径 $0$，剩下 $24$ 栋房子。

数据范围与提示

详细子任务附加限制及分值如下表所示。