Candy

There are NNN children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

(1) Each child must have at least one candy.

(2) Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Input:

The input consists of multiple test cases.

The first line of each test case has a number NNN, which indicates the number of students.

Then there are NNN students rating values, 1≤N≤300,1≤values≤100001 \leq N \leq 300, 1 \leq values \leq 100001≤N≤300,1≤values≤10000.

Output:

The minimum number of candies you must give.

样例1

输入：

51 2 3 4 55 1 3 5 3 6

输出：

159 好题， 3 3 3 1

#include 
      
       #define N 301int num[N], pro[N];int main(){    int n;    while(scanf("%d", &n) != EOF)    {        for(int i=0; i< n; i++)             scanf("%d", &pro[i]);        num[0]= 1;        for(int i=1; i
       
         pro[i-1])                num[i]=num[i-1]+1;            else                num[i]=1;        }                 for(int i=n-2; i>=0; i--) //从后向前扫描        {            if(pro[i] >pro[i+1] && num[i] <= num[i+1])            {                num[i]= num[i+1]+1;            }        }                int sum= 0;        for(int i=0; i< n; i++)        {               sum += num[i];        }        printf("%d\n", sum);    }    return 0;}