Салюти
На честь дня міста мерія вирішила влаштувати салют. Для цього було замовлено батарею салютів, яка складається з послідовності зв'язаних між собою залпових пристроїв, які по черзі спрацьовують, починаючи з першого. При спрацюванні вони викидають у небо піроелементи, які вибухають на певній висоті. Для кожного пристрою відомо на якій висоті відбудеться вибух. Керівництво міста забажало, щоб кожен наступний вибух відбувався на більшій висоті, ніж попередні і згідні ради цього пожертвувати навіть кількістю залпів. Проте хоча б один залп обов'язково повинен бути. Деякі пристрої можуть бути відключені і тоді вони не будуть викидати піроелементи, але послідовність спрацювань не може бути змінена.
Напишіть програму, яка визначить скількома способами піротехник може виконати вимоги керівництва міста.
Вхідні дані
У першому рядку задано єдине ціле число N (1 ≤ N ≤ 2000). У другому рядку задано N натуральних чисел. i-те число визначає висоту h_i, на якій відбувається вибух елементів, випущених з i-го пристрою. Числа h_i не перевищують 10000.
Вихідні дані
У єдиному рядку виведіть одне число - кількість варіантів запуску салюта, кожен наступний вибух якого буде вище попереднього.