Stalpi

Cerință

În ciudatul oraș al Micului Gates, primăria a instalat pe o stradă $n$ stâlpi pentru iluminat, dispusi în linie, la distanțe egale între ei, de $1$ metru. Fiecare stâlp este identificat unic prin poziția sa în șir, de la $1$ la $n$. Primul stâlp se află la poziția $1$ (la începutul străzii), al doilea stâlp la poziția $2$ și așa mai departe, până la poziția $n$, unde se află ultimul stâlp (unde se termină strada). Ciudățenia constă în faptul că stâlpii au înălțimi diferite, fiecare stâlp asigurând o iluminare a zonei în care se află pe o distanță egală în stânga și în dreapta sa cu înălțimea stâlpului. De exemplu, dacă un stâlp are înălțimea $x$, el va asigura iluminarea pe o distanță egală cu $x$ metri în stânga și $x$ metri în dreapta sa (inclusiv poziția pe care se află). Înălțimea fiecărui stâlp este cunoscută.

Micul Gates primește de la primărie sarcina de a răspunde următoarelor cerințe:

1. Care este cea mai mare diferență de înălțime între doi stâlpi consecutivi în șir?
2. Care este numărul minim de stâlpi care trebuie păstrați, astfel încât strada să fie complet iluminată?

Date de intrare

Fișierul de intrare stalpi.in conține:

• pe prima linie o valoare $1$ sau $2$ reprezentând numărul cerinței care trebuie rezolvată;
• pe a doua linie un număr întreg $n$, reprezentând numărul de stâlpi;
• pe a treia linie $n$ numere naturale nenule separate printr-un spațiu, unde al $i$-lea număr reprezintă înălțimea stâlpului de la poziția $i$.

Date de ieșire

Pe prima linie a fișierului de ieșire stalpi.out se va găsi un singur număr reprezentând răspunsul în conformitate cu cerința care trebuie rezolvată.

Restricții și precizări

• $2 \leq n \leq 10^6$;
• Pentru cerința $1$ se acordă $32$ de puncte;
• Pentru cerința $2$ se acordă $68$ de puncte. Dintre acestea, pentru $24$ de puncte, $n \leq 10^3$;
• Pentru toate testele, $1 \leq h_i \leq 10^3$ pentru oricare $i$ între $1$ și $n$.

Exemplul 1

stalpi.in

1
3
5 10 8

stalpi.out

5

Explicație

Diferența maximă dintre doi stâlpi vecini este 5 (dintre stâlpul 1 si stâlpul 2).

Exemplul 2

stalpi.in

2
10  
1 2 1 1 3 1 2 1 1 1  

stalpi.out

3

Explicație

Cel mai mic număr de stâlpi de care avem nevoie este 3.
$1 \ \mathbf{2} \ 1 \ 1 \ \mathbf{3} \ 1 \ 2 \ 1 \ 1 \ \mathbf{1}$ (stâlpul de pe poziția 2, cel de pe poziția 5 și cel de pe poziția 10)

Exemplul 3

stalpi.in

2
10
1 1 1 1 1 1 1 1 1 1

stalpi.out

4

Explicație

$1 \ \mathbf{1} \ 1 \ 1 \ \mathbf{1} \ 1 \ 1 \ \mathbf{1} \ 1 \ \mathbf{1}$. Avem nevoie de $4$ stâlpi.
Primul stâlp ales acoperă pozițiile de la $1$ la $3$, inclusiv acestea.
Al doilea stâlp ales acoperă pozițiile de la $4$ la $6$, inclusiv acestea.
Al treilea stâlp ales acoperă pozițiile de la $7$ la $9$, inclusiv acestea.
Al patrulea stâlp ales acoperă pozițiile de la $9$ la $10$, inclusiv acestea.