Problem 63: Candy Distribution

Problem Statement: Given an array representing the ratings of children standing in a line, distribute candies so that each child gets at least one candy and children with a higher rating than an immediate neighbor get more candies. Compute the minimum candies required.

Input

The first line contains an integer n. The second line contains n space-separated integers representing the ratings.

Output

Print the minimum number of candies required.

Examples


Input:
3
1 0 2

Output:
5

Solution Explanation

Perform two passes: one from left to right ensuring right neighbor condition and one from right to left. Sum the maximum values obtained from both passes for each index.

Solution in C++


#include 
#include 
#include 
using namespace std;

int main(){
    int n; 
    cin >> n;
    vector ratings(n);
    for(int i = 0; i < n; i++)
        cin >> ratings[i];
    vector candies(n, 1);
    for(int i = 1; i < n; i++){
        if(ratings[i] > ratings[i - 1])
            candies[i] = candies[i - 1] + 1;
    }
    for(int i = n - 2; i >= 0; i--){
        if(ratings[i] > ratings[i + 1])
            candies[i] = max(candies[i], candies[i + 1] + 1);
    }
    int ans = 0;
    for(auto c : candies)
        ans += c;
    cout << ans << "\n";
    return 0;
}