eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Салюти

Салюти

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

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

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

Вхідні дані

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

Вихідні дані

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

Приклад

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