题目描述

Ingrid, the apple farmer, has just harvested a huge amount of apples that she intends to give to herself and her neighbours. Her neighbourhood can be represented by an infinite plane where every point with integer coordinates contains exactly one house. Ingrid's house is located at the origin $(0, 0)$. Ingrid has a special strategy when distributing apples. First, she selects a list of $n$ non negative integers $r_1, r_2, \cdots, r_n$. For each number in the list, she then gives one apple to every house within radius $r_i$, i.e. every house whose coordinates satisfy $x^2 + y^2 \leq r_i^2$ (including her own). That way, Ingrid's close neighbours get more apples than her distant neighbours.

Ingrid has just chosen the list of radii, but then a problem arose. When distributing apples she always puts them in cube-shaped boxes with eight apples in each box. Therefore, it is very important that the total number of apples distributed is a multiple of eight. Ingrid needs to remove some radii from the list so that the number of given apples becomes a multiple of eight. It is always possible to do so, for example by removing all radii, but Ingrid does not want to appear greedy so she wants to remove radii in a way that minimizes the number of apples not given among the ones she originally planned to give. Your task is to find this minimum.

输入格式

• Line 1: The integer $N$, namely the number of radii ($1 \leq N \leq 3 \cdot 10^5$).
• Line 2: The integers $r_1, r_2, \ldots, r_N$ separated by space ($0 \leq r_i \leq 3 \cdot 10^5$).

输出格式

• Print one integer, the minimum number of apples Ingrid can refrain from distributing by removing radii from her list, in such a way that the total number of distributed apples becomes a multiple of eight.

6
1 0 2 1 0 0

2

提示

Within a radius of: 0 there is 1 house, 1 there are 5 houses, and 2 there are 13 houses. In total there are thus 26 houses within the radii. By removing the two radii 0 there are 24 remaining houses.

Scoring

Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.