După ce ai studiat problema subşirului crescător de lungime maximală, ai adăugat următoarea condiţie:
dacă există mai multe subşiruri crescătoare maximale, atunci se va alege acel subşir care are maximul diferenţelor în modul ale elementelor consecutive cât mai mic posibil.
Mai exact, dacă avem subşirul crescător: Ai1 Ai2 ... Aik atunci maximul diferenţelor este max (Ai2 – Ai1, Ai3 – Ai2, ... , Aik – Aik-1). Vom numi acest maxim cost al subşirului.
Cerinţă
Dat fiind un şir de numere, scrie un program care să determine lungimea unui subşir crescător maximal, precum şi costul minim al unui astfel de subşir.
Date de intrare
Fişierul de intrare subs.in va conţine pe prima linie numărul natural N, reprezentând numărul de elemente din şir. Pe a doua linie se află N numere naturale, separate prin spaţii, reprezentând elementele şirului.
Date de ieşire
Fişierul de ieşire subs.out va conţine o singură linie pe care se află două numere naturale separate printr-un spaţiu: lungimea subşirului crescător maximal, respectiv costul minim.
Restricţii
1 ≤ N ≤ 30 000
Elementele şirului sunt numere naturale din intervalul [1, 1 000 000 000]
Pentru 40% din teste N ≤ 2500.
Exemplu
subs.in
subs.out
Explicatie
6
2 1 5 4 7 5
3 2
Subşirul crescător maximal căutat este: 2 4 5
Lungimea lui este: 3
Diferenţa maximă este: max (4 - 2, 5 – 4) = 2, care este minim posibilă.
Daca luăm subşirul 1 4 7 diferenţa maxima este 3, ceea ce nu este optim.