라인 타운

Line Town의 주민 $N$명이 일렬로 서 있다. 처음에 주민들의 행복도는 왼쪽에서 오른쪽 순서로 $h_{1}, h_{2}, \ldots, h_{N}$이다.

당신은 Line Town의 시장으로서 "공동체, 사탕, 조직"(CCO) 계획의 세 번째 기둥을 시행하고 있다. 시장은 주민들의 자리를 바꿀 권한이 있다. 한 번의 교환에서 인접한 두 주민에게 줄 안에서 자리를 맞바꾸라고 지시할 수 있다. 다만 이 교환으로 두 주민의 행복도는 모두 부호가 바뀐다.

주민들의 행복도가 왼쪽에서 오른쪽으로 갈수록 작아지지 않도록 교환을 여러 번 수행하려 한다. 가능한지 판단하고, 가능하다면 필요한 교환 횟수의 최솟값을 구하라.

첫째 줄에 정수 $N$이 주어진다. 둘째 줄에는 왼쪽부터 오른쪽 순서로 주민들의 행복도 $h_{1}, \ldots, h_{N}$ $(-10^{9} \le h_{i} \le 10^{9})$이 공백으로 구분되어 주어진다.

한 줄에 교환 횟수의 최솟값을 출력한다. 불가능하면 -1을 출력한다.

$1 \le N \le 500\,000$