Salutes#3005
To celebrate the city's anniversary, the city hall has decided to organize a fireworks display. They have ordered a series of interconnected fireworks devices that activate sequentially, starting with the first one. Each device, when activated, launches pyrotechnic elements that explode at a specific altitude. The city management wants each subsequent explosion to occur at a higher altitude than the previous one, even if it means reducing the number of salvos. However, at least one salvo must be fired. Some devices can be disabled, meaning they will not launch any pyrotechnic elements, but the order of activation cannot be changed.
Write a program to determine the number of ways the pyrotechnician can configure the fireworks to meet the city management's requirements.
The first line contains a single integer (1 \leq N \leq 2000). The second line contains natural numbers. The -th number specifies the height h_i at which the elements from the -th device explode. The numbers h_i do not exceed .
Output a single number — the number of ways to launch the fireworks such that each subsequent explosion is at a higher altitude than the previous one.
Example 1