Vedere

Orașul Townsville are nevoie de un nou sistem de supraveghere! Primarul dorește să reducă costurile așa că vă prezintă planul orașului și vă cere ajutorul.

Townsville poate fi reprezentat printr-un sistem de coordonate carteziene în plan, în care axa $OX$ reprezintă nivelul solului. Acesta este alcătuit din n blocuri, dispuse pe axa $OX$, pe poziții cu abscise naturale consecutive, de la $1$ la $n$. Pentru fiecare bloc $i$, se cunoaște înălțimea acestuia $h_i$. Cu alte cuvinte, blocul $i$ ($1 \leq i \leq n$) este segmentul care unește punctul de coordonate $(i, 0)$, baza blocului, de punctul $(i, h_i)$, vârful blocului.

Primarul dorește să amplaseze o cameră de luat vederi, la o poziție de coordonate naturale din plan, cu abscisa cuprinsă între $1$ și $n$ ($1 \leq x \leq n$), din care atât primul cât și ultimul bloc să poată fi observate de cameră. Camera are vedere către un bloc dacă segmentul ce unește camera de vârful blocului nu intersectează alte blocuri (acest segment poate însă intersecta alte vârfuri de bloc, fără ca vederea să fie obturată). De asemenea, camera nu poate fi plasată în interiorul unui bloc, dar poate fi plasată oriunde în exterior sau chiar în vârful unuia dintre blocuri.

Determinați punctul de ordonată minimă (coordonata $y$/înălțimea minimă) în care poate fi amplasată camera. Dacă există mai multe puncte cu ordonată minimă care satisfac cerința, dintre acestea afișați-l pe cel cu abscisa (coordonata $x$) minimă.

Date de intrare

Fișierul vedere.in conține pe prima linie un număr $n$ care reprezintă numărul de blocuri. Pe linia a doua se află $n$ valori naturale reprezentând înălțimile blocurilor în ordinea numerotării lor de la $1$ la $n$.

Date de ieșire

Fișierul vedere.out conține coordonatele $x$ și $y$ ale punctului căutat (numere naturale separate prin spațiu).

Restricții și precizări

• $2 \leq n \leq 100 \ 000$;
• $1 \leq h_i \leq 1 \ 000 \ 000 \ 000$, oricare ar fi $1 \leq i \leq n$;
• Se garantează că $y$ căutat este maxim $1 \ 000 \ 000 \ 000$.
• Pentru teste în valoare de $18$ puncte: $n$, înălțimile blocurilor și $y$ căutat $\leq 5 \ 000$;
• Pentru alte teste în valoare de $13$ puncte: $n \leq 5 \ 000$ și punctul căutat se află în vârful unui bloc;
• Pentru alte teste în valoare de $24$ puncte: punctul căutat se află în vârful unui bloc;
• Pentru alte teste în valoare de $18$ puncte: $n \leq 5 \ 000$.

Exemplul 1

vedere.in

14
2 1 2 3 4 1 6 4 6 7 7 1 4 4

vedere.out

10 8

Explicație

În primul exemplu, plasând camera la coordonatele $(10, 8)$, atât primul bloc, cât și ultimul sunt vizibile. Observați că segmentele care unesc camera de blocurile $1$, respectiv $n$, intersectează și vârfurile blocurilor $7$, respectiv $11$. Aceste intersecții sunt permise și nu obturează vederea.

Exemplul 2

vedere.in

2
10 20

vedere.out

1 10

Explicație

În cel de-al doilea exemplu, plasând camera în vârful blocului $1$, obținem punctul de ordonată minimă din care ambele blocuri sunt vizibile.