Милан тврди дека смислил нов начин за сортирање на низа од броеви.

Дадена е низа A составена од N цели броеви, индексирани од 0 до N-1.

Помеѓу секои два соседни елементи има по еден „споредувач“. Секој споредувач работи само со елементите до него. Ако тие два елементи се во погрешен редослед, тој ги заменува.

Споредувачите работат во рунди, на следниот начин:
Во непарни рунди (првата, третата, петтата, …), работат споредувачите што ги споредуваат паровите (A₀, A₁), (A₂, A₃), (A₄, A₅), … Ако левиот елемент е поголем од десниот, тие два елементи ги менуваат местата. Ако N е непарен, тогаш последниот елемент нема пар и не се менува во таа рунда.
Во парни рунди (втората, четвртата, шестата, …), работат споредувачите што ги споредуваат паровите (A₁, A₂), (A₃, A₄), (A₅, A₆), … Повторно, ако левиот елемент е поголем од десниот, тие два елементи ги менуваат местата. Елементот A₀ никогаш не се менува во парна рунда. Ако N е парен, тогаш и последниот елемент нема пар и не се менува во таа рунда.

Процесот продолжува се' додека низата не стане сортирана во неопаѓачки редослед. Низата е сортирана во неопаѓачки редослед ако за секое i важи: A_i ≤ A_i+1.

Ваша задача е да одредите колку рунди ќе се извршат пред низата првпат да стане сортирана.

Влез

Првата линија содржи еден цел број N (1 ≤ N ≤ 100 000).
Втората линија содржи N цели броеви A₀, A₁, …, A_N-1 (0 ≤ A_i ≤ 10⁹).

Забелешка. За 20% од поените важи: N ≤ 2 000.
За други 10% од поените важи: За секој A_i важи дека или A_i = X или A_i = Y, за некои вредности X и Y.

Излез

Отпечатете еден цел број – бројот на рунди што ќе се извршат пред низата да стане сортирана во неопаѓачки редослед.

Ограничувања

Временско ограничување: 200 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
4
4 3 2 1

излез
4

влез
4
3 1 2 2

излез
3

влез
4
0 5 5 0

излез
2