Studnia

Limit pamięci: 64 MB

Bajtazar wybrał się na wyprawę wzdłuż Suchej Rzeki, która przecina Pustynię Bajtocką. Niestety Sucha Rzeka wyschła, a Bajtazarowi skończyła się woda. Jedynym ratunkiem dla Bajtazara jest wykopanie studni na dnie wyschniętego koryta rzeki i dokopanie się do wody.

Bajtazar postanowił dobrze przemyśleć, co ma zrobić, zanim weźmie się za kopanie - wie, że jeśli opadnie z sił, a nie dokopie się do wody, to będzie miał skrajnie małe szanse na przetrwanie. Udało mu się określić, na jakiej głębokości pod dnem rzeki zalega woda. Wie też, na ile kopania starczy mu sił. Boi się tylko, żeby w czasie kopania nie osunęła się ziemia, gdyż może go pogrzebać żywcem. Bajtazar przesłał Ci (przez telefon satelitarny) opis topografii koryta rzeki. Poprosił Cię o wyznaczenie planu, gdzie ma kopać, tak aby dokopać się do wody, zanim opadnie z sił, a równocześnie, żeby zbocza w wykopie były jak najłagodniejsze. Bajtazar czeka na Twoją pomoc!

Wejście

W pierwszym wierszu standardowego wejścia są zapisane dwie dodatnie liczby całkowite i (, ), oddzielone pojedynczym odstępem. W drugim wierszu znajduje się dodatnich liczb całkowitych (), pooddzielanych pojedynczymi odstępami.

Bajtazarowi zostało sił na ruchów łopatą. Liczby stanowią opis topografii koryta Suchej Rzeki, zdatnego do kopania studni. Liczby te reprezentują grubość warstwy piasku ponad poziomem wody gruntowej, w kolejnych miejscach, co metr wzdłuż koryta rzeki. Jednym ruchem łopaty Bajtazar może wybrać tyle piachu, aby jedną z liczb zmniejszyć o 1. Jeżeli którakolwiek z liczb , powiedzmy , zmniejszy się do 0, będzie to oznaczać, że Bajtazar dokopał się do wody. Poza dokopaniem się do wody w co najmniej jednym punkcie koryta rzeki, Bajtazarowi zależy na tym, aby na końcu następująca liczba , charakteryzująca nachylenie piaszczystych zboczy:

była jak najmniejsza. Jeżeli istnieje wiele poprawnych wartości liczby , reprezentującej miejsce, w którym Bajtazar powinien dokopać się do poziomu wody, Twój program powinien wypisać dowolną z nich. Możesz przyjąć, że poza miejscami na wszystkich głębokościach znajduje się lita skała oraz że Bajtazar zawsze będzie miał wystarczająco dużo siły, żeby w którymś miejscu dokopać się do wody.

W testach wartych co najmniej 35% punktów zachodzi dodatkowy warunek .

Wyjście

Twój program powinien wypisać na standardowe wyjście dwie liczby całkowite oddzielone pojedynczym odstępem: miejsce , w którym Bajtazar powinien dokopać się do wody, oraz najmniejszą możliwą wartość liczby .

Przykład

Dla danych wejściowych:

16 15
8 7 6 5 5 5 5 5 6 6 7 8 9 7 5 5

poprawną odpowiedzią jest:

1 2

Na powyższym rysunku prawidłowy wykop Bajtazara oznaczono szarym kolorem.

Autor zadania: Michał Włodarczyk.