Problem description

Po długich tułaczkach Karol w końcu wylądował w Warszawie, teraz zostało jeszcze tylko wsiąść do samochodu i za dwie godzinki dojechać do domu.

Karol wsiadał już do samochodu, gdy ostatni raz spojrzał na panoramę N warszawskich wieżowców i tak się złożyło, że wszystkie z nich widoczne były jeden przy drugim w rzędzie. Przyjrzał się im uważnie i zauważył, że każdy z nich ma parzystą liczbę pięter, a ponadto nie ma dwóch budynków o jednakowej liczbie pięter. Podróżnik zaczął się zastanawiać nad tym ile inwersji, czyli takich par budynków, że wyższy stoi na lewo od niższego, jest obecnych w panoramie warszawskich wieżowców. Policzył to szybko, wsiadł do samochodu i odjechał.

W drodze jednak coś nie dawało mu spokoju, zastanawiał się nad tym, ile najwięcej inwersji mogłoby być obecnych w warszawskiej panoramie, gdyby któremuś z budynków dobudować lub zburzyć nieparzyście wiele pięter.

Niestety ta zagadka przerosła Karola i to Twoim zadaniem będzie napisanie programu, który wczyta wysokości kolejnych budynków warszawskiej panoramy i wyznaczy maksymalną liczbę inwersji, jaką można uzyskać po dobudowaniu lub zburzeniu nieparzystej liczby pięter jednego, dowolnego budynku.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, oznaczająca liczbę budynków obecnych w warszawskiej panoramie. W drugim wierszu wejścia znajduje się ciąg N liczb A_i, pooddzielanych pojedynczymi odstępami i oznaczający wysokości kolejnych budynków w panoramie od lewej do prawej.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba naturalna – maksymalna liczba inwersji, jaką można uzyskać po dobudowaniu lub zburzeniu nieparzyście wielu pięter dowolnego budynku.

Ograniczenia

1 ≤ N ≤ 100 000, 2 ≤ A_i ≤ 10⁹.

Przykład

8
30 16 4 2 10 12 14 8

21