클론 전쟁

카미노 행성에서 만들어진 클론 군대는 드로이드와 싸우는 제다이를 도왔다. 팰퍼티과 「명령 66」을 내리자 모든 것이 바뀌었다. 클론들은 경고도 없이 제다이를 공격했다. 그러나 밝은 편의 희망이 완전히 사라진 것은 아니었다. 명령을 듣지 못한 일부 클론은 제다이 편에서 계속 싸웠다. 그래서 모든 제다이가 죽은 뒤에도 전쟁은 끝나지 않았다. 팰퍼틴의 명령에 따라 모든 클론은 마지막 전투를 위해 한 줄로 늘어섰다.

요다는 제국 측 클론과 제다이에게 충성을 지킨 공화국 측 클론을 구별하는 법을 배워야 한다는 것을 깨달았다. 전장을 살펴본 요다는 각 클론에게 그 클론이 서 있는 자리에 맞는 좌표를 붙였다. 포스를 사용해 요다는 전장의 클론 배치를 바꾸었다. 같은 편에 속한 어떤 두 클론 사이의 거리는 짝수가 되고, 적대하는 편에 속한 어떤 두 클론 사이의 거리는 홀수가 되었다. 두 클론이 같은 위치에 서 있는 경우는 없다. 그렇게 클론 전쟁이 시작되었다.

승산을 가늠하기 위해 요다는 서로 싸울 수 있는 클론 쌍의 개수를 알고 싶어 한다. 즉, 쌍을 이루는 두 클론이 서로 다른 편에 속하는 쌍의 개수이다.

첫 줄에 최종 전투에 참여하는 클론의 수 $n$ ($1 \le n \le 100000$)이 주어진다. 다음 줄에는 클론의 좌표 $a_i$ ($1 \le a_i \le 10^9$) $n$개가 주어진다. 모든 $a_i$는 서로 다르다.

서로 싸울 수 있는 클론 쌍의 개수를 한 줄에 출력한다.