Question
Number of Groups
Given an array arr[] of n distinct integers. Find the count of groups of 2 or 3 integers that can be formed by choosing integers from the given array such that sum of integers in each of the group is divisible by three.
NOTE: Answer can be very large.
Input
The first line of input will take an integer as input representing n.
The second line of input will take n space-separated integers representing elements of array arr.
Constraints:
1 ≤ n ≤ 105
1 ≤ arr[i] ≤ 105
The second line of input will take n space-separated integers representing elements of array arr.
Constraints:
1 ≤ n ≤ 105
1 ≤ arr[i] ≤ 105
Output
Print an integer representing a count of groups of 2 or 3 integers that can be formed by choosing integers from the given array such that the sum of integers in each of the groups is divisible by three.
NOTE: Answer can be very large.
NOTE: Answer can be very large.
Example
Input:
4
1 2 3 5
Output:
4
Explanation:
There are only 4 possible groups: (1,2,3);
(1,2) ; (1,5) ; (1,3,5)
Input:
3
1 1 1
Output:
1
Explanation:
There is only 1 possible group: (1,1,1).
4
1 2 3 5
Output:
4
Explanation:
There are only 4 possible groups: (1,2,3);
(1,2) ; (1,5) ; (1,3,5)
Input:
3
1 1 1
Output:
1
Explanation:
There is only 1 possible group: (1,1,1).