题目描述

给定数组 $a=[a_1,a_2,\cdots,a_n]$，Eve 可以执行任意次（可能 $0$ 次）以下操作：

• 选择 $1\leq i\leq n$，令 $a_i\gets a_i+1$。

Eve 希望最终数组中任意三个相邻元素之和都是 $3$ 的倍数。

请求出需要达成目标所需的最小操作次数。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,\cdots,a_n$。

输出格式

一行一个整数表示答案。

3
1 3 5

0

样例解释 1

1+3+5=9，是 3 的倍数，不需要操作。

10
2 3 10 25 12 7 10 12 1 46

3

样例解释 2

对 i=4,7,10 分别操作一次。

数据范围

对于 $30\%$ 的数据，$3\leq n\leq 5$。

对于 $60\%$ 的数据，$3\leq n\leq 1000$。

对于 $100\%$ 的数据，$3\leq n\leq 10^5$，$1\leq a_i\leq 10^9$。