Vulcani

Time limit: 1s Memory limit: 64MB Input: vulcani.in Output: vulcani.out

Bob merge în vacanță pe insula Vulcanilor unde se află NN vulcani, poziționați de la 11 la NN. Fiecare vulcan are o înățime cunoscută, HH, care este un număr pozitiv pentru vulcanii de tipul 11, care se află pe pământ și un număr negativ pentru vulcanii de tipul 22, care se află sub pământ. Un vulcan este numit special dacă nu există niciun vulcan de același tip, aflat pe o poziție mai mare decât a sa, pentru care modulul înălțimii este mai mare sau egal decât modulul înălțimii sale.
Pe insulă există un buton care poate muta un vulcan de pe pământ, sub pământ sau un vulcan de sub pământ, pe pământ. Bob vrea să afle care este numărul maxim de vulcani speciali care se pot obține, folosind acel buton o singură dată.

Date de intrare

Fișerul de intrare vulcani.in conține pe prima linie un număr natural nenul NN care reprezintă numărul de vulcani. Pe următoarea linie se vor afla NN numere întregi care reprezintă inăltimile vulcanilor.

Date de ieșire

Fișierul de ieșire vulcani.out va conține pe prima linie numărul maxim de vulcani speciali care se pot obține.

Restricții și precizări

  • 1N1051 \leq N \leq 10^5
  • 109H109−10^9 \leq H \leq 10^9
  • Pentru teste in valoare de 1010 puncte N100N \leq 100.
  • Pentru alte teste in valoare de 2525 de puncte N1 000N \leq 1 \ 000.
  • Pentru alte teste in valoare de 2525 de puncte 106H106−10^6\leq H \leq 10^6.
  • Pentru alte teste în valoare de 4040 de puncte, nu există restricții suplimentar

Exemplul 1

vulcani.in

6
7 9 -5 2 3 -4

vulcani.out

5

Exemplul 2

vulcani.in

5
6 8 8 4 -9

vulcani.out

3

Explicații

Pentru primul exemplu, răspunsul se obține prin folosirea butonului pentru primul sau cel de-al doilea vulcan. După această schimbare, vulcanii de pe pozitiile 1,2,3,51, 2, 3, 5 și 66 sunt speciali.
Pentru al doilea exemplu, inițial vulcanii de pe pozițiile 3,43, 4 și 55 sunt speciali. Schimbând tipul vulcanilor de pe pozițiile 1,21, 2 sau 33 se obține numărul maxim care este egal cu numărul inițial de vulcani speciali.

Log in or sign up to be able to send submissions!