After fiddling with numbers for too long, Mr. DeMello has decided to work with spooky arrays! However, he is not very good with them; he has had a question on his mind for a while but cannot solve it, so he asks you for help:
Given an array, find the number of valid solutions for , where are strictly increasing .
Can you help him?
For all subtasks:
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [70%]
The first line will contain , the number of array elements.
The second line will contain space-separated integers, , the elements of the array.
Output the number of valid solutions to the given equation .
8 1 1 2 3 1 1 2 3
Explanation for Sample Output
The valid solutions are , , , .
Note that the indices are 1-indexed.