eolymp
Competitions

III Stage UOI Donetsk, 2012 I Tour 10-11 kl.

Салюты

В честь дня города мэрия решила устроить салют. Для этого была заказана батарея салютов, которая состоит из последовательности связанных между собой залповых устройств, которые поочередно срабатывают, начиная с первого. При срабатывании они выбрасывают в небо пироэлементы, которые взрываются на определенной высоте. Для каждого устройства известно на какой высоте произойдет взрыв. Руководство города пожелало, чтобы каждый последующий взрыв происходил на большей высоте, чем предыдущий и согласно ради этого пожертвовать даже количеством залпов. Однако хотя бы один залп обязательно должен быть. Некоторые устройства могут быть отключены и тогда они не будут выбрасывать пироэлементы, но последовательность срабатываний не может быть изменена.

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

Входные данные

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

Выходные данные

В единственной строке выведите одно число - количество вариантов запуска салюта, каждый следующий взрыв которого будет выше предыдущего.

Time limit 1 second
Memory limit 64 MiB
Input example #1
2
1 2
Output example #1
3
Author Кравцов Д.В.
Source III этап УОИ Донецк, 2012 г. I тур 10-11 кл.