Задача Parkur. Вам подарували гру, в якій паркурист стрибає по дахах хмарочосів. На кожному рівні гри генерується новий проспект з хмарочосів, де кожна висотка задається унікальною додатною координатою відносно початку проспекту. Після цього обирається будівля, з якої паркурист розпочинає свій шлях, при цьому він може стрибати тільки на будівлю, координата якої більша за поточну. Складність цієї гри полягає в тому, що після кожного стрибка герой втомлюється і вже не може стрибати так далеко як раніше. Формально кажучи, на кожному рівні генерується n будівель, координати яких рівні a1;a2;…;an. Гравець обирає стартовий хмарочос і з нього може стрибнути на будь-яку будівлю, яка знаходиться правіше, при цьому довжина першого стрибка може бути будь-якою. Для усіх подальших стрибків справедлива умова: якщо зараз гравець знаходиться на будівлі з координатою ai, а до цього був на позиції aj, то він може перестрибнути на будівлю з координатою ak, якщо ai-aj>ak-ai. Для кожного рівня знайдіть максимальну кількість хмарочосів, яку можна відвідати.
Технічні умови. Програма parkur читає з пристрою стандартного введення кількість будівель на даному рівні гри n (1≤n≤5000) і позиції цих будівель a1;a2;…;an (0≤ai≤1018; ai≠aj, якщо i≠j ). Гарантується, що сума n не перевершує 30 000. Програма виводить на стандартний пристрій виведення максимальну кількість хмарочосів, яку можна відвідати.
Приклади
Введення
5 9 19 3 8 6
Виведення
4
Введення
3 16 5 17
Виведення
3
Коментар
У першому прикладі оптимальний вибір хмарочосів 3; 5; 4; 1, їхні координати 3; 6; 8; 9.