CSES - Lauta-aita
  • Time limit: 4.00 s
  • Memory limit: 128 MB

Uolevin vuosia sitten rakentama lauta-aita ei täytä enää EU-direktiiviä. Sen vuoksi Uolevi joutuu korjaamaan aitaansa.

Direktiivin mukaan lauta-aidassa tulee olla kaksi osuutta: ensin jokaisen laudan tulee olla edellistä korkeampi, sitten jokaisen laudan tulee olla edellistä matalampi. Osuuksien pituudet voivat olla mitä tahansa, ja jompikumpi osuus voi olla tyhjä.

Uolevilla menee minuutti vaihtaa keskenään kaksi vierekkäistä lautaa. Kuinka nopeasti Uolevi pystyy korjaamaan aitansa direktiivin mukaiseksi?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: lautojen määrä aidassa.

Seuraavalla rivillä on n kokonaislukua a_1,a_2,\ldots,a_n: jokaisen laudan korkeus.

Aidassa ei ole kahta lautaa, joiden korkeus olisi sama.

Tuloste

Ohjelman tulee tulostaa yksi kokonaisluku: kuinka monta minuuttia Uolevilla menee aidan korjaamiseen.

Rajat

  • 1 \le n \le 10^5
  • 1 \le a_k \le 10^9

Esimerkki

Syöte:

5
2 5 1 3 7

Tuloste:

3

Selitys: Uolevi vaihtaa ensin laudat 1 ja 3, sitten laudat 1 ja 7 ja lopuksi laudat 3 ja 7. Nyt laudat ovat järjestyksessä 2, 5, 7, 3, 1 ja aita on direktiivien mukainen.