disasteryes
BAN USER- 0of 0 votes
AnswersThe person who wrote this problem is going through the bad phase of his life. But, fortunately he won some cash in his last programming event.
- disasteryes in India
Now to make his girlfriend feel special, he wants to buy her some chocolates. As mentioned, he is not having good time so he want to spend as less as possible.
Keeping that in mind, he decided to play a game with her. The rule of game is as follows:
1) There are N chocolates represented by type 1..N
2) He will arrange them in a row in some random order
3) Now she (his girlfriend ofcourse) has to pick an index say i, then she will get all the chocolates at index j such that j>i and type of chocolate at j is strictly less than type of chocolate at index i.
He believes that his girlfriend is not that clever and will surely not choose the most optimal index, but he wants to know that if by any chance she picked the optimal index then how many chocolates will he have to buy.
Input:
First line contain N. then next line contain N space separated integers.
output :
A single integer which is the answer.
Constraints :
1 ≤ N ≤ 105
1<=A[i]<=10^5
Sample Input (Plaintext Link)
10
7 6 10 5 2 8 1 9 3 4
Sample Output (Plaintext Link)
7
Explanation
If she chooses i=3, then all the elements in right of i have type less than 10, hence ans is 7. In none of the other case she can get more chocolates.| Report Duplicate | Flag | PURGE
fd SDE1 Algorithm