Clone War

The clone army built on the planet Kamino helped the Jedi fight the droids. Everything changed when Palpatine issued Order 66: without warning, the clones attacked the Jedi. But the Light Side had not lost everything. Some clones did not hear the order and kept fighting on the Jedi's side. So the war did not end when all the Jedi were killed. On Palpatine's orders, all the clones lined up in a single row for the final battle.

Master Yoda realized he must learn to tell the Imperial clones apart from the Republic clones who stayed loyal to the Jedi. Surveying the field, Yoda assigned each clone a coordinate matching the spot where it stands. Using the Force, the master rearranged the clones on the field so that the distance between any two clones on the same side is even, and the distance between any two clones on opposing sides is odd. No two clones stand at the same position. And the clone war began...

To estimate their chances of winning, Master Yoda wants to know the number of pairs of clones that can fight each other, that is, the number of pairs whose clones serve different sides.

The first line contains the number of clones $n$ ($1 \le n \le 100000$) taking part in the final battle. The next line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$), the coordinates of the clones. All $a_i$ are distinct.

Print a single number: the number of pairs of clones that can fight each other.