Contest problemset description

Tej nocy Karol śnił wyjątkowo dobrze, bowiem odwiedziło go mnóstwo snów przygodowych, a każdy z nich był wypchany wrażeniami z egzotycznego kraju. Karol nie wierzył w takie rzeczy jak przeznaczenie objawione we śnie. Nie mniej jednak sam pomysł kilku wyszukanych podróży zdecydowanie przypadł mu do gustu. Znany ze swojej gotowości do działania, już następnego ranka był w Pekinie i tak właśnie zaczęły się przygody podróżnika Karola.

Karol, przechadzając się po typowo azjatyckich parkach, dostrzegł, że sporo młodzieży przesiaduje w licznych grupkach, pochłoniętych rozgrywką w pewną chińską grę. Chcąc zapewnić sobie trochę rozrywki intelektualnej, nasz podróżnik przysiadł na ławce i przyglądał się uważnie rozgrywce.

Gra sama w sobie okazała się dość prosta, należy się przede wszystkim zaopatrzyć w karty i figurki przedstawiające rozmaite potworki, a następnie wystawić jedną ze swoich figurek na karcie i porównać jej moc z mocą figurki wystawionej przez przeciwnika. Formalne zasady gry brzmią następująco:

• wygrywa gracz, którego moc wystawionej figurki jest większa;
• każdy potworek ma swoją moc M i jeden z czterech żywiołów T: W – woda, O – ogień, P – powietrze, Z – ziemia;
• opis każdej karty składa się z bonusów dla każdego z czterech żywiołów;
• karta wzmacnia lub osłabia potworka, który na niej stoi, zwiększając lub zmniejszając jego moc zgodnie z bonusem przynależnym jego żywiołowi;
• dodatkowo, niektóre z żywiołów dominują nad innymi, dokładnie: woda dominuje nad ogniem, ogień dominuje nad powietrzem, powietrze dominuje nad ziemią, a ziemia dominuje nad wodą;
• gdy potworek walczy z przeciwnikiem, którego dominuje żywiołem, to jego moc i bonus są podwajane.

Karol zdążył się już zaopatrzyć w rozkładane figurki potworki i całkiem pokaźną talię kart. Już za chwilę dołączy do rozgrywki i zmierzy się ze swoim pierwszym przeciwnikiem – Quangiem. By mieć zwycięstwo w kieszeni postanowił przygotować sobie program, który po wczytaniu opisów potworków i kart, na których stoją, szybko wyznaczy wynik pojedynku. Tutaj cały plan “wziął w łeb”, bo podczas pospiesznego pakowania się Karol zapomniał spakować laptopa, tak więc to Twoim zadaniem będzie napisanie programu dla naszego podróżnika.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita M_K i jedna litera T_K, oddzielone pojedynczym odstępem i oznaczające odpowiednio moc potworka Karola oraz jego żywioł. W drugim wierszu wejścia znajdują się cztery liczby całkowite W_K, O_K, P_K i Z_K, oznaczające odpowiednio bonusy karty, na której stoi figurka Karola dla żywiołów woda, ogień, powietrze i ziemia.

W trzecim wierszu wejścia znajduje się jedna liczba całkowita M_Q i jedna litera T_Q, oddzielone pojedynczym odstępem i oznaczające odpowiednio moc potworka przeciwnika Karola oraz jego żywioł. W czwartym wierszu wejścia znajdują się cztery liczby całkowite W_Q, O_Q, P_Q i Z_Q, oznaczające odpowiednio bonusy karty, na której stoi figurka Quanga – przeciwnika Karola dla żywiołów woda, ogień, powietrze i ziemia.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinno się znaleźć jedno słowo WYGRANA, PRZEGRANA lub REMIS, w zależności od rezultatu pojedynku.

Ograniczenia

 − 10⁶ ≤ M_K, W_K, O_K, P_K, Z_K, M_Q, W_Q, O_Q, P_Q, Z_Q ≤ 10⁶, T_K, T_Q ∈ {W, O, P, Z}.

Przykład

60 W
80 -10 30 100
80 W
20 70 200 -30

WYGRANA

200 P
0 -20 100 400
140 O
0 20 -100 -20

PRZEGRANA

100 Z
20 -20 20 20
140 O
20 -20 20 20

REMIS

Po wizycie w Pekinie Karol za następny cel podróży obrał sobie Dubaj. W Dubaju jest bowiem najwyższy budynek na świecie, w którym jest najdłuższa na świecie winda i to właśnie ona szczególnie zainteresowała Karola – stał więc cały dzień w głównym holu budynku, obserwując wyświetlacz zamontowany nad drzwiami do windy, i zapisywał sobie numery pięter, na których kolejno stawała rzeczona winda.

Karol chciałby się dowiedzieć ile razy winda zmieniła swój zwrot ruchu, czyli ile razy z jazdy w górę przeszła do jazdy w dół lub odwrotnie.

Po całym dniu obserwowania windy Karol jest już zmęczony i poprosił Cię o pomoc w rozwiązaniu tej zagadki.

Napisz program, który wczyta numery pięter, na których kolejno stawała winda, wyznaczy ile razy zmieniła zwrot ruchu i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się dodatnia liczba całkowita N oznaczająca liczbę numerów pięter zapisanych przez Karola. W drugim wierszu wejścia znajduje się N nieujemnych liczb całkowitych A₁, A₂, …, A_N pooddzielanych pojedynczymi odstępami i oznaczających kolejne numery pięter, na których stawała winda.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna nieujemna liczba całkowita oznaczająca ile razy winda zmieniła zwrot ruchu.

Ograniczenia

1 ≤ N ≤ 1 000 000, 0 ≤ A_i ≤ 10⁹, A_i ≠ A_i + 1 dla wszystkich i < N.

Przykład

6
8 3 4 5 7 6

2

5
6 5 3 2 0

0

7
1 3 4 3 5 4 6

4

Po przygodzie w znanej na cały świat krainie hazardu podróżnik Karol postanowił wybrać się do miejsc trochę bliższych kolebce ludzkości. Nic więc dziwnego, że zdecydował się na podróż do Kairu, by podziwiać tam słynne piramidy. Dotarł na miejsce w samo południe, gdy słońce górowało, a upalne powietrze było nie do wytrzymania.

Podróżnik nie mógł oprzeć się pokusie podejścia do antycznych grobowców trochę bliżej, niż jest to dozwolone. Oczywiście jego decyzje były wtedy ułatwiane przez srogi żar z nieba, a chęć odetchnięcia w niewielkim cieniu piramidy niezwykle kusiła. Pech chciał, że pod wpływem gorąca Karol stracił czujność i gdy podchodził do piramidy, spadł do niewielkiej groty przy niej. Oczywiście nic mu się nie stało, a wręcz przeciwnie, grota sprawiała wrażenie, jakby nikogo w niej nie było od setek lat – miała więc dla podróżnika ogromną wartość turystyczną.

Wieczorem, po powrocie do luksusowego hotelu, gdy Karol przeglądał zdjęcia z groty pod piramidami, ujrzał specyficznie wyglądające hieroglify i z braku lepszego zajęcia spróbował rozszyfrować ich znaczenie. Uczynił już spore postępy – udało mu się częściowo rozszyfrować wiadomość tak, że składała się z wystąpień jedynie dwóch liter: H i Y. Niestety tutaj kończą się dobre wiadomości – oświetlenie w hotelu było złe, łóżko zbyt mało luksusowe, ogólnie wszystko było nie takie, jakie być powinno, a brak laptopa zdecydowanie nie pomagał w tej sytuacji. Przez to zaszyta w hieroglifach wiadomość nie dała się do końca rozszyfrować. Na szczęście dzięki dogłębnej analizie podróżnik wie, że pomylił się na dokładnie jednej pozycji wiadomości i zamienił H na Y lub Y na H. Do tego Karol wie nawet, w jaki dokładnie sposób wyznaczyć miejsce pomyłki, niestety bez komputera nie będzie to takie proste. Miejscem pomyłki będzie taka skrajnie lewa pozycja, że zamiana litery na niej, zmaksymalizuje liczbę wystąpień podciągu HY. Dla przypomnienia, mając dany napis, jego podciąg może być uzyskany poprzez zmazanie z niego pewnej liczby liter i odczytanie pozostałych liter od lewej do prawej. Na przykład, słowo HYHY zawiera 3 podciągi HY – złożone odpowiednio z pierwszej i drugiej litery, pierwszej i czwartej litery oraz trzeciej i czwartej litery.

Twoim zadaniem będzie napisanie programu, który wyznaczy pozycję błędu i poda Karolowi już poprawioną wiadomość – taką o zmaksymalizowanej liczbie wystąpień podciągu HY. Karol będzie już wtedy wiedział jak dokończyć rozszyfrowanie wiadomości.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, oznaczająca długość wiadomości do korekty. W drugim wierszu wejścia znajduje ciąg N znaków H i Y, reprezentujący tekst wiadomości.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinno znaleźć się jedno słowo złożone z liter H i Y – wiadomość po korekcie, czyli takiej jednej zamianie znaku, po której liczba wystąpień podciągu HY jest maksymalna.

Ograniczenia

1 ≤ N ≤ 100 000.

Przykład

8
HYHYYYHY

HHHYYYHY

6
HHHYYY

HHYYYY

6
HYHYYY

HHHYYY

2
HY

YY

Po dniu pełnym atrakcji w Dubaju Karol postanowił udać się do Las Vegas, gdzie jego rosnące zainteresowanie teorią prawdopodobieństwa i dysponowanie nienagannymi manierami skłoniły go do zostania krupierem.

Karol otwierał właśnie stół do gry w pokera, gdy przypomniał sobie, że z jednym z N graczy siedzących przy tym stole wiążą go zażyłości towarzyskie. By lekko dopomóc jego szczęściu, Karol postanowił, że “wytasuje” znajomemu strita przy rozdawaniu kart. Proces rozdawania kart w kasynie Karola jest maszynowy – krupier wkłada do maszyny talię kart, a ta samodzielnie rozdaje karty graczom. W maszynie jest już talia kart i teraz Karol zastanawia się, ile co najmniej zamian kart musi wykonać, by jego znajomy na pewno dostał strita. Przez zamianę kart rozumiemy wybranie dwóch kart z maszyny i włożenie pierwszej w miejsce drugiej i drugiej w miejsce pierwszej.

Strit to układ kart – pięć kart o następujących po sobie wartościach, przy czym karty nie mogą być wszystkie jednego koloru (strit tworzą np. karty 4, 5, 6, 7 w kolorze karo i 8 w kolorze trefl). As może być zarówno najwyższą kartą (strit 10 J Q K A), jak i najniższą (strit A 2 3 4 5), jednak zakazane jest tworzenie stritów, w których as ma podwójną rolę (np. K A 2 3 4).

Maszyna rozdaje karty w taki sposób, że gracz o numerze k otrzymuje k-tą, (N+k)-tą, (2N+k)-tą, (3N+k)-tą i (4N+k)-tą kartę z talii.

Znajomy Karola zawsze jest graczem nr 1.

Napisz program, który wczyta liczbę graczy i opis talii znajdującej się w maszynie, wyznaczy liczbę ręcznych zamian kart z talii wystarczającą do zapewnienia strita graczowi nr 1 i wypisze ją na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna dodatnia liczba całkowita N, określająca liczbę graczy. W drugim wierszu wejścia znajdują się 52 opisy kolejnych kart z talii pooddzielane pojedynczymi odstępami.

Opis karty składa się z dwóch następujących bezpośrednio po sobie części: pierwsza to wartość oznaczana przez jeden spośród napisów A, K, Q, J, 10, 9, …, 2, natomiast druga to kolor oznaczany przez jeden spośród napisów s, h, c, d (spades, hearts, clubs, diamonds).

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna nieujemna liczba całkowita oznaczająca minimalną liczbę zamian kart w talii potrzebnych do zagwarantowania graczowi nr 1 strita.

Ograniczenia

2 ≤ N ≤ 10, karty opisane na wejściu tworzą permutację talii.

Przykład

Dla czytelności drugi wiersz każdego zestawu danych został ręcznie podzielony. W zestawach danych, na których testowane są programy, zawsze są dokładnie dwa wiersze (jak opisano w sekcji Wejście).

2
5c Jh 4c 9h 6c 5h 3s Qs 7d
Jc 9d 4s 2s 7h 6d 2d 7s As 
8s Ac 9c 6h 4d 8d 5s 8h Qd 
Kd 9s Kh 6s 10s Qh 2c 3h Ks 
5d 3d 10c Js Ah 8c Jd 10h 3c 
2h Kc Ad 7c Qc 4h 10d 

0

2
3h 2c 4h As 5c 9s 4c 6s 6d 
5d 5s Jh Jc 6h 9d 3s 7h Kh 
2h 10d 4d 10s Kc Qc 3c 8c Kd 
8h 7c 10c Jd Ah Js 9h 3d Qh 
Ad 10h 4s Qd 2d 8d 8s Qs 7s 
6c 5h Ks 9c 7d 2s Ac 

1

4
2s 2c 7c 6h Jd Qs 10s 9c Qd 
3c 9h 4c 10d 6d 8d 4h Kd Qh 
8h 5c Kh 7h 4s 5h Ac Kc Ks 
Js 6s 3h 2h Ah 9d Ad 5d 8c 
3s Jc As 3d 9s 5s Qc 10h 10c 
2d 7s 7d 4d 6c 8s Jh 

1

Karol znowu przemieścił się między kontynentami i tym razem zatrudnił się przy budowie słynnej Drogi Panamerykańskiej.

Zadaniem Karola jest ustawienie znaków ostrzegawczych przed niebezpieczeństwami na jednej z jednokierunkowych jezdni tej drogi zgodnie z poniższymi regułami:

• Każdy znak musi być przykręcony do słupa. Słupy zostały już wbite w ziemię i Karol wie dokładnie w jakich miejscach drogi.
• Na każdym słupie mogą być co najwyżej trzy znaki.
• Każde niebezpieczeństwo na drodze wymaga postawienia znaku co najmniej A i co najwyżej B metrów przed.
• Każdy znak może informować o tylko jednym niebezpieczeństwie.

Pomóż Karolowi ustawić znaki lub stwierdź, że takie ustawienie nie istnieje.

Napisz program, który wczyta pozycje niebezpieczeństw i słupów, wyznaczy odpowiednie przypisanie znaków do słupów lub rozstrzygnie, że takie nie istnieje i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie dodatnie liczby całkowite N i M oddzielone pojedynczym odstępem i oznaczające odpowiednio liczbę niebezpieczeństw i liczbę słupów wbitych przy drodze.

W drugim wierszu wejścia znajdują się dwie dodatnie liczby całkowite A i B oddzielone pojedynczym odstępem i oznaczające odpowiednio minimalną i maksymalną odległość od znaku do niebezpieczeństwa.

W trzecim wierszu wejścia znajduje się N dodatnich liczb całkowitych D₁, D₂, …, D_N pooddzielanych pojedynczymi odstępami i oznaczających odległości (w metrach) kolejnych niebezpieczeństw od początku drogi.

W czwartym wierszu wejścia znajduje się M dodatnich liczb całkowitych S₁, S₂, …, S_M pooddzielanych pojedynczymi odstępami i oznaczających odległości (w metrach) kolejnych słupów od początku drogi.

Wyjście

W pierwszym wierszu wyjścia powinno znaleźć się słowo TAK lub NIE, w zależności od tego czy istnieje rozwiązanie.

Jeśli rozwiązanie istnieje, należy wypisać N kolejnych wierszy. W i-tym z nich powinna znaleźć się jedna dodatnia liczba całkowita oznaczająca numer słupa, na którym został umieszczony znak odpowiadający i-temu z kolei niebezpieczeństwu.

Uwaga: dla niektórych zestawów testowych więcej niż jedna odpowiedź jest poprawna.

Ograniczenia

1 ≤ N, M ≤ 100 000, 1 ≤ A ≤ B ≤ 10⁹, 1 ≤ D₁ ≤ D₂ ≤ ⋯ ≤ D_N ≤ 10⁹, 1 ≤ S₁ < S₂ < ⋯ < S_M ≤ 10⁹.

Przykład

3 2
10 20
50 55 70
40 60

TAK
1
1
2

4 3
15 30
10 20 40 80
5 35 85

NIE

6 2
100 200
300 310 320 330 340 350
100 200

NIE

Wizyta na kontynentach oddalonych od Europy o Ocean Atlantycki dłużyła się Karolowi; postanowił więc, że już czas wracać do domu. Kupił możliwie najszybszy bilet lotniczy do Warszawy i tak się akurat złożyło, że był z kilkugodzinną przesiadką w Paryżu; nasz podróżnik nie mógł oczywiście zmarnować okazji do krótkiego zwiedzania stolicy Francji.

Karol postanowił wybrać się na Pola Elizejskie, na których właśnie odbywał się festiwal Bomb Francuskich – słynny na cały świat pokaz fajerwerków.

Pola Elizejskie mają kształt prostokątnego placu o wymiarach N × M metrów i mogą zostać w oczywisty sposób podzielone na N ⋅ M kawałków jednostkowych. Kawałek jednostkowy może być jednoznacznie wyznaczony poprzez podanie jego współrzędnych X i Y. Władze umieściły już na niektórych kawałkach jednostkowych placu fajerwerki dwóch różnych typów: HS – Hałaśliwych Serpentyn i AL – Ambrozji Leistej.

Fajerwerki typu HS mają moc R_HS i gdy wybuchają, to pokrywają niebo nad wszystkimi kawałkami jednostkowymi placu, które odległe są w metryce Manhattan o nie więcej niż R_HS – jeśli wystrzelony zostaje fajerwerk typu HS z kawałka jednostkowego o współrzędnych X_F i Y_F, to pokrywa wszystkie kawałki jednostkowe Pola Elizejskiego, których współrzędne X_P i Y_P spełniają zależność |X_F−X_P| + |Y_F−Y_P| ≤ R_HS.

Fajerwerki typu AL mają moc R_AL i gdy wybuchają, to pokrywają niebo nad wszystkimi kawałkami jednostkowymi placu, które odległe są w metryce Maksimum o nie więcej niż R_AL – jeśli wystrzelony zostaje fajerwerk typu AL z kawałka jednostkowego o współrzędnych X_F i Y_F, to pokrywa wszystkie kawałki jednostkowe Pola Elizejskiego, których współrzędne X_P i Y_P spełniają zależność max(|X_F−X_P|,|Y_F−Y_P|) ≤ R_AL.

Niestety ze względu na konieczność powrotu na lotnisko, jak i faktu opóźnienia się pokazu przez warunki atmosferyczne, Karol nie doczekał się wystrzału fajerwerków. Teraz zastanawia się nad tym, jak duże były ich moce. Podróżnik jest pewien, że po pierwsze fajerwerki pokryły niebo nad każdym kawałkiem jednostkowym Pola Elizejskiego; a po drugie, że ze względu na ograniczony budżet suma mocy fajerwerków R_HS i R_AL była najmniejsza możliwa.

Twoim zadaniem będzie napisanie programu, który wczyta rozłożenie fajerwerków na Polu Elizejskim i wyznaczy minimalną sumę mocy fajerwerków R_HS i R_AL, dla której możliwe jest pokrycie nieba nad każdym kawałkiem jednostkowym Pola Elizejskiego.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i M, oddzielone pojedynczym odstępem i oznaczające odpowiednio wysokość i szerokość Pola Elizejskiego. W każdym z kolejnych N wierszy znajduje się ciąg M znaków określających zawartość poszczególnych kawałków jednostkowych Pola Elizejskiego:

• . – oznacza kawałek jednostkowy, na którym nie został umieszczony żaden fajerwerk,
• A – oznacza kawałek jednostkowy, na którym umieszczony został fajerwerk typu AL,
• H – oznacza kawałek jednostkowy, na którym umieszczony został fajerwerk typu HS.

Zagwarantowane jest, że na Polu Elizejskim znajduje się przynajmniej jeden fajerwerk.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba naturalna – minimalna suma mocy fajerwerków R_HS i R_AL, dla której możliwe jest pokrycie nieba nad każdym kawałkiem jednostkowym Pola Elizejskiego.

Ograniczenia

1 ≤ N, M ≤ 1 000.

Przykład

5 13
.............
.H...........
........A....
.H...........
.............

7

Przejechawszy całą Drogę Panamerykańską, Karol zawrócił i pojechał do Nowego Jorku, gdzie, zaintrygowany niezwykłą regularnością układu tamtejszych ulic, postanowił zostać taksówkarzem.

Na telefonie Karola działa aplikacja Taxi Driver, która pokazuje mu dostępne zlecenia opisane punktem początkowym, końcowym i zapłatą w dolarach za wykonanie kursu. Nowy Jork jest na tyle dużym miastem, że nawet jeśli Karol wykona jakieś zlecenie, to po chwili i tak znajdzie się kolejna osoba, która potrzebuje przejechać tę samą trasę za tę samą opłatę – innymi słowy zlecenia nie wygasają.

Dla uproszczenia przyjmujemy, że interesujący Karola fragment Nowego Jorku to sieć ulic, z których każde dwie są równoległe lub prostopadłe i każde dwie sąsiednie równoległe ulice są od siebie oddalone o 1 km, a ponadto początek i koniec każdego zlecenia to skrzyżowanie dwóch ulic. Przyjmiemy więc układ współrzędnych, w którym (x,y) to skrzyżowanie x-tej ulicy w kierunku północ-południe z y-tą ulicą w kierunku wschód-zachód. W szczególności odległość między punktem (x,y) i punktem (x′,y′) to |x−x′| + |y−y′| kilometrów.

Przejechanie jednego kilometra zawsze kosztuje Karola 1 dolara, a jego dzień pracy zaczyna się w punkcie (1,1) i kończy w punkcie (X_K,Y_K), co oznacza, że Karol może być danego dnia stratny, bo i tak musi przejechać z (1,1) do (X_K,Y_K).

Jaki największy zysk może osiągnąć Karol? Czy Karol może wybierać zlecenia tak, by zarobić dowolnie dużo?

Napisz program, który wczyta opis zleceń dostępnych w aplikacji Taxi Driver, wyznaczy optymalny scenariusz jazdy dla Karola i wypisze maksymalny zysk na standardowe wyjście lub poinformuje, że Karol może zarobić dowolnie dużo.

Wejście

W pierwszym wierszu wejścia znajdują się trzy dodatnie liczby całkowite N, X_K, Y_K, pooddzielane pojedynczymi odstępami i oznaczające kolejno: liczbę zleceń dostępnych w aplikacji Taxi Driver i położenie punktu końcowego.

W każdym z kolejnych N wierszy wejścia znajduje się pięć dodatnich liczb całkowitych X_S, i, Y_S, i, X_E, i, Y_E, i, Z_i, pooddzielanych pojedynczymi odstępami i oznaczających, że istnieje zlecenie przewozu z punktu (X_S, i,Y_S, i) do punktu (X_E, i,Y_E, i), za które Karol otrzyma Z_i dolarów.

Wyjście

Jeśli Karol może uzyskać dowolnie duży zysk, to w jedynym wierszu wyjścia powinno znaleźć się słowo KREZUS.

W przeciwnym razie, w jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita określająca maksymalny zysk Karola w dolarach.

Ograniczenia

1 ≤ N ≤ 2 000, 1 ≤ X_⋅,i, Y_⋅,i, X_K, Y_K ≤ 1 000 000, 1 ≤ Z_i ≤ 10 000 000.

Przykład

1 10 10
4 3 7 8 10

-8

1 5 3
10 10 20 20 25

-6

2 3 4
2 2 8 3 12
6 2 4 5 9

KREZUS

3 8 6
5 5 4 10 9
5 8 8 5 9
2 2 5 4 8

2

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