You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

老师要奖励N名成绩优秀的同学，首先N名同学按随机顺序排成一排，且每名同学都对应一个成绩（成绩 各不相同)，然后按照如下规则进行奖励。

规则：

1)每名同学至少奖励1支铅笔

2)每一名同学拿到铅笔后，都会和左右相邻的同学作比较，如果相邻的同学成绩比自己高，那么铅笔数也一定比自己多，如果相邻的同学成绩比自己低，那么铅笔数一定比自己少。（注意每个人成绩都不同）

当给出要奖励的同学数N,及名同学的成绩及排序位置，请你按照规则帮助老师计算出最少需要奖励多少支铅笔。

例如： 当N=3,3名同学的成绩分别为：91,92,94 如果3名同学的排序为：91,94,92，最少需要奖励4支铅笔（成绩为91的同学1支，成绩为94的同学2支， 成绩为92的同学1支)： 如果3名同学的排序为：91,92,94，最少需要奖励6支铅笔（成绩为91的同学1支，成绩为92的同学2支， 成绩为94的同学3支)。

输入描述

第一行输入一个正整数N,N表示要奖励的同学数 第二行输入N个正整数，每个正整数表示一名同学的成绩（成绩各不相同），正整数之间以空格隔开，正整数的顺序即代表学生的排序。

输出描述：

输出一个整数，表示N名同学最少需要奖励的铅笔数。

3
91 94 92

4

数据范围

N <= 100