e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Задачі

Салюти

Салюти

На честь дня міста мерія вирішила влаштувати салют. Для цього було замовлено батарею салютів, яка складається з послідовності зв'язаних між собою залпових пристроїв, які по черзі спрацьовують, починаючи з першого. При спрацюванні вони викидають у небо піроелементи, які вибухають на певній висоті. Для кожного пристрою відомо на якій висоті відбудеться вибух. Керівництво міста забажало, щоб кожен наступний вибух відбувався на більшій висоті, ніж попередні і згідні ради цього пожертвувати навіть кількістю залпів. Проте хоча б один залп обов'язково повинен бути. Деякі пристрої можуть бути відключені і тоді вони не будуть викидати піроелементи, але послідовність спрацювань не може бути змінена.

Напишіть програму, яка визначить скількома способами піротехник може виконати вимоги керівництва міста.

Вхідні дані

У першому рядку задано єдине ціле число N (1N2000). У другому рядку задано N натуральних чисел. i-те число визначає висоту hi, на якій відбувається вибух елементів, випущених з i-го пристрою. Числа hi не перевищують 10000.

Вихідні дані

У єдиному рядку виведіть одне число - кількість варіантів запуску салюта, кожен наступний вибух якого буде вище попереднього.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
2
1 2
Вихідні дані #1
3
Автор Кравцов Д.В.
Джерело III этап УОИ Донецк, 2012 г. I тур 10-11 кл.