Alice is a teacher of kindergarten. She wants to give some candies to the children in her class. All the children sit in a line and each of them has a rating score according to his or her usual performance. Alice wants to give at least 1 candy for each children. Because children are somehow jealousy. Alice must give her candies according to their ratings subjects to for any adjacent 2 children if one's rating is higher than the other he/she must get more candies than the other. Alice wants to save money so she wants to give as few as candies in total.
Input The first line of the input is an integre N, the number of children in Alice's class. Each of the following N lines contains an integer indicates the rating of each child. Ouput On the only line of the output print an integer describing the minimum number of candies Alice must give. Sample Input 3 1 2 2 Sample Ouput 4 Explanation The number of candies Alice must give are 1,2 and 1. Constraints: N and the rating of each children is no larger than 10^5. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
