print2064. Война клонов

printВойна клонов

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Армия клонов, созданная на планете Камино, помогала джедаям сражаться против дроидов. Все изменилось, когда Палпатин отдал "Приказ 66": без предупреждения клоны напали на джедаев. Но не все еще потеряно для Светлой стороны. Некоторые клоны не услышали приказ и продолжили сражаться на стороне джедаев. Поэтому война не закончилась, когда все джедаи были убиты. По приказу Палпатина все клоны выстроились в одну линию для финальной битвы.
Магистр Йода понял, что он должен научиться отличать имперских клонов и клонов Республики, которые остались верны джедаям. Оглядев поле, Йода присвоил каждому клону координату, соответствующую месту, где стоит клон. С помощью Силы магистр изменил расстановку клонов на поле так, что расстояние между любыми двумя клонами одной стороны стало четно, а между любыми двумя клонами вражеских сторон – нечетно. При этом никакие два клона не стоят на одной позиции. И началась война клонов…
Чтобы оценить шансы на победу, магистр Йода хочет знать количество пар клонов, которые могут сразиться между собой, то есть количество пар таких, что клоны в паре служат разным сторонам.
В первой строке входного файла задано число `n` (`1\ ≤\ n\ ≤\ 100000`) – число клонов, участвующих в финальной битве. В следующей строке заданы `n` чисел `a_i` (`1\ ≤\ a_i\ ≤\ 10^9`) – координаты клонов, все `a_i` различны.
В выходной файл выведите единственное числов – количество пар клонов, которые могут сразиться между собой.

Пример ввода

5
1 2 3 4 5

Пример вывода

6
Источник: neerc.ifmo.ru/school
loading