C. Улыбающиеся числа

Вибачте, але цю сторінку ще не перекладено на українську мову For the sake of viewer convenience, the content is shown below in one of the available alternative languages. You may click one of the links to switch the site language to another available language.

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

About the post author Igor Mazurok (5 Posts)

PhD in Computer Science, Associate professor of Department Applied Mathematics of Odessa I.I.Mechnikov National University, Ukraine KBIS Software Developer

Author Info

Igor Mazurok

PhD in Computer Science, Associate professor of Department Applied Mathematics of Odessa I.I.Mechnikov National University, Ukraine
KBIS Software Developer

Leave a Reply