Mr.Chan gives some candies to a group of students, one student at a time. Each student will get 4 candies more than the preceding one. The sixth student gets 40 candies. BASED ON THIS SITUATION ANSWER THE FOLLOWING
The common difference is
8
16
2
4
17. How much candies got by the first student
20
16
12
24
18. How much candies 10th student will get ?
50
52
54
56
19. If he is having totally 80 candies, how many students he can give candies ?
16
12
14
15
20. Find the number of candies got by 15th student
Answers
There are n number of students in a class. Each student is rated with some performance score. The teacher wants to distribute candies to the students such that each students gets at least one candy. If the two students sitting next to each other then one with higher ratings must get more candies. What is the minimum number of candy required to distribute in the class.
Constraints: 1 <= n <= 10^5 1 <= ratings <= 10^5
Input and Output format:
First line of the input contains n i.e. number of students. Followed by n numbers representing rating of respective student. Output the minimum number of candies required.
SAMPLE INPUT
3
1 2 2
SAMPLE OUTPUT
4
Explanation
All the students must get at least 1 candy so total number candies is 3. But since the 2 nd student has higher rating i.e. 2 that the first one i.e. 1 hence 2 nd student must be getting 2 candies, hence total number of candies is 4.
Time Limit: 0.2 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB