Description

给你一个数组 $a_1, a_2, \ldots, a_n$ 。

在一次操作中，你可以执行以下两种操作中的任何一种：

• 从数组中选择一个元素并将其删除。这样，数组的长度会减少 $1$ ；
• 从数组中选择一个元素，并将其数值增加 $1$ 。

您可以执行任意次数的操作。如果当前数组为空，则不能再操作。

你的任务是找出使数组中的元素之和 $a$ 能被 $3$ 整除所需的 最少 步数。

注意空数组（长度为 $0$ 的数组）的元素之和等于 $0$ 。

Format

Input

第一行输入一个数字 $n$

第二行输入 $n$ 个控股隔开的数字分别代表 $a_1,a_2,\cdots,a_n$

Output

输出一个整数代表答案。

Samples

4
2 2 5 4

1

3
1 3 2

0

2
5 5

2

Limitation

在第一个测试案例中，最初是数组 $a = [2, 2, 5, 4]$ 。操作的最佳方法之一是移除当前的第 $4$ 个元素，得到 $a = [2, 2, 5]$，这样，数组 $a$ 的元素之和就能被 $3$ 整除（实际上是 $a_1 + a_2 + a_3 = 2 + 2 + 5 = 9$ ）。

在第二个测试案例中，一开始数组的和是 $1+3+2 = 6$ ，可以被 $3$ 整除。因此不需要移动。因此，答案是 $0$ 。

在第三个测试案例中，一种操作的办法是删去第一个数字，数组 $a=[5]$，然后让数组中剩余的唯一一个数字加 $1$，数组变为 $a=[6]$，其和是 $3$ 的倍数。

对于 $100\%$ 的数据满足， $1\leq n\leq 10^5$，$1\leq a_i\leq 10^4$