2 sec, 256 M

*I will never forget your eyes, your smile*

Leonid Nerushenko

It is not a secret that the ONU students write the most original diploma works. For example, Innocent Nestruyko, student of the Welfare Grocery Totalitarian Systems Department, dedicated his work study of the properties of so-called "smiling numbers". He considers the sequence of natural numbers and looking at them, a "smiling couple". According to the theory of a smiling, it is such a pair of numbers a, b, that b > a and b at the same time is later in the sequence than a. In addition, the number c must be placed between a and b, such that a > c and the sum of a + b + c is divisible by 3. As student Nestruyko easily find all the pairs in the mind, and the diploma work pages need something to fill in, he asks you to write a program that would search the "smiling pairs". Innocent promised not to stay in debt and contribute you to be credited to his department.

Input. The first line of input contains an integer N (1 ≤ N ≤ 100000) – the length of the sequence. The second line contains the elements of the sequence, separated by spaces. All elements are natural numbers not exceeding 300,000.

Output. Print a single number – the number of the required "smiling pairs".

Input | Output |

4
5 4 6 3 |
1 |

Idea – Oleg Alexandrovich Petrov

### Igor Mazurok

KBIS Software Developer

#### Latest posts by Igor Mazurok (see all)

- Best of coders - 03/03/2013
- Most popular compiler - 03/03/2013
- Rating software firms - 03/03/2013