Профильная информатика:
подготовка к ЕГЭ и олимпиадам

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21^Р 22 23 24 25 26 27

Дан набор из N неотрицательных целых чисел. Необходимо определить количество троек элементов (ai,aj,ak) этого набора, в которых 1 ≤ i < j < k ≤ N и сумма элементов кратна 12.

Напишите эффективную по времени и по памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения переменных программы, не превышает одного килобайта и не увеличивается с ростом N.

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел N (3 ≤ N ≤ 10000). В каждой из последующих N строк записано одно неотрицательное целое число, не превышающее 1000.

Пример входных данных:

	5
	7
	5
	6
	12
	24

Пример выходных данных для приведённого выше примера входных данных:

	2

В приведённом наборе из 5 чисел имеются две тройки — (7,5,12) и (7,5,24), сумма элементов которых кратна 12.