Məsələlər
Салюты
Салюты
В честь дня города мэрия решила устроить салют. Для этого была заказана батарея салютов, которая состоит из последовательности связанных между собой залповых устройств, которые поочередно срабатывают, начиная с первого. При срабатывании они выбрасывают в небо пироэлементы, которые взрываются на определенной высоте. Для каждого устройства известно на какой высоте произойдет взрыв. Руководство города пожелало, чтобы каждый последующий взрыв происходил на большей высоте, чем предыдущий и согласно ради этого пожертвовать даже количеством залпов. Однако хотя бы один залп обязательно должен быть. Некоторые устройства могут быть отключены и тогда они не будут выбрасывать пироэлементы, но последовательность срабатываний не может быть изменена.
Напишите программу, которая определит сколькими способами пиротехник может выполнить требования руководства города.
\InputFile
В первой строке задается единственное целое число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{2000}). Во второй строке задаются \textbf{N} натуральных чисел. \textbf{i}-ое число определяет высоту \textbf{h_i}, на которой происходит взрыв элементов, выпущенных из \textbf{i}-го устройства. Числа \textbf{h_i} не превосходят \textbf{10000}.
\OutputFile
В единственной строке выведите одно число - количество вариантов запуска салюта, каждый следующий взрыв которого будет выше предыдущего.
Giriş verilənləri #1
2 1 2
Çıxış verilənləri #1
3