1971:Розрізання
Переглянути як PDFНа довгій стрічці одне за одним записані ~N~ цілих чисел – усі цілі числа від 1 до ~N~. Кожне з цих чисел записане рівно один раз і повторюваних чисел немає. Числа необов'язково писати в порядку зростання (від меншого до більшого). Між кожними двома числами є пробіл. Ми можемо розрізати стрічку там, де є пробіли. Мета полягає в тому, щоб, розрізавши стрічку, ми могли потім переставити шматки стрічки (не обертаючи їх) так, щоб в отриманій послідовності числа були розташовані в порядку зростання.
Напишіть програму, яка знаходить найменшу кількість розрізів, які ми можемо зробити, щоб розташувати отримані частини вказаним чином?
Input
Перший рядок містить одне ціле число ~N~ (~1 \le N \le 1 000 000~).
Наступні ~N~ рядків містять цілі числа - числа зі стрічки в тому порядку, в якому вони були записані на стрічку.
Output
Виведіть два цілі числа, розділені рівно одним пробілом: кількість зроблених розрізів і кількість чисел у найдовшій частині стрічки, отриманої в результаті розрізів.
Sample Input 1
12
12
1
2
4
5
6
7
10
11
3
8
9
Sample Output 1
5 4
Notes
Місце кожного розрізу позначається знаком |:
12 | 1 2 | 4 5 6 7 | 10 11 | 3 | 8 9
Найдовша частина стрічки після розрізів містить числа 4 5 6 7 і їх кількість 4.
Коментарі
Змінено формат вхідних даних - тепер числа вводяться з окремих рядків
що таке invalid return?
помилка вводу-виводу.
Зверніть увагу на обмеження по памʼяті!