Приборкання стада
Рано вранці фермер Джон прокинувся від звуку тріску дерева. Це були корови, і вони знову вибігали з корівника!
Фермеру Джону вже набридли ранкові втечі корів, і він вирішив, що досить: пора стати жорстким. Він прибив до стіни сараю лічильник, що відстежує кількість днів з моменту останнього прориву. Таким чином, якщо прорив стався вранці, лічильник у той день був би 0; якщо останній прорив був 3 дні тому, лічильник покаже 3. Фермер Джон щодня ретельно реєстрував лічильник.
Кінець року настав, і фермер Джон готовий вести бухгалтерський облік. Він каже, що корови заплатять! Але о диво, деякі записи в його журналі відсутні!
Фермер Джон впевнений, що він почав свій журнал у день втечі. Будь ласка, допоможіть йому визначити з усіх послідовностей подій, що узгоджуються з рештою записів у журналі, мінімальну та максимальну кількість втеч, які могли мати місце протягом зареєстрованого часу.
Вхідні дані
Перша рядок містить єдине ціле число n (1 ≤ n ≤ 100) - кількість днів з тих пір, як фермер Джон почав реєструвати лічильник виходу корів.
Друга рядок містить n цілих чисел. Якщо i-те число дорівнює -1, то це вказує на відсутність запису в журналі для дня i. Не від'ємне ціле число a[i]
(не більше 100) вказує на те, що в день i лічильник показував a[i]
.
Вихідні дані
Якщо послідовність подій не відповідає частковому протоколу фермера Джона та його знанням про те, що корови безумовно вибралися з корівника вранці дня 1, виведіть єдине ціле число -1. В іншому випадку виведіть два цілі числа: m і M, де m - мінімальна кількість виходів з будь-якої узгодженої послідовності подій, а M - максимальна.
Приклад
У цьому прикладі ми можемо зробити висновок, що прорив повинен був статися в день 3. Знаючи, що прорив також стався в день 1, єдина залишкова частина невизначеності полягає в тому, чи стався прорив у день 2. Відповідно, всього було від 2 до 3 проривів.