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