There are NN 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 NN, which indicates the number of students.

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

Output:

The minimum number of candies you must give.

样例1

输入：

5
1 2 3 4 5
5
1 3 5 3 6

输出：

15
9

贪心。调了半天。扫两遍

/* ***********************************************
Created Time :2016/4/24 17:15:25
File Name :1.cpp
************************************************ */
#include
#include
#include
#include
#include
#include
#include
#include
#include

bool cmp(int a,int b){
return a>b;
}
int a[maxn];
int b[maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
//freopen("out.txt","w",stdout);
int n;
while(cin>>n){
for(int i=;i>a[i];
int tmp=;
cle(b);
for(int i=;ia[i-])b[i]=max(tmp++,b[i]);
else tmp=;
}
tmp=;
for(int i=n-;i>=;i--){
if(a[i]>a[i+])b[i]=max(tmp++,b[i]);
else tmp=;
}
int sum=;
for(int i=;i<=n;i++)sum+=b[i];
cout<<sum+n<<endl;
}
return ;
}