An array of N integers is said to be trivisible iff the sum of each of its non-empty subarrays is divisible by 3. For example, [1, 2, 3] is not trivisible as the sum of the subarray [2, 3] is not divisible by 3. On the other hand, [3, -6] is trivisible.
Mancunian was given the following problem by his friend Liverbird. He is given an array which may or may not be trivisible. His task is to convert it to a trivisible array using some number of moves. In each move, he can choose any element of the current array and delete it.
Find the minimum number of moves to be made by Mancunian.
Input:
The first line contains a single integer N denoting the number of elements in the array A[].
The second line contains N integers denoting the elements of the array.
Output:
Output a single integer which is the answer to the problem.
Constraints:
1 <= N <= 1000
0 <= |Ai| <= 106