问题 o: 小H分糖果(动态规划)

问题 o: 小H分糖果(动态规划)

时间限制: 1 Sec  内存限制: 128 MB
提交: 1582  解决: 1160
[提交][状态][讨论版][命题人:]

题目描述

小H来到一个小学分糖果,小学生们很听话,站成一排等着分糖果,小H将根据每个人的上次考试分数给一定的糖果,规则如下。

  • 每个人都有自己分数ai,代表上次考试成绩。
  • 每个人都至少有一颗糖。
  • 如果两个人相邻,分数高的一定比分数低的糖果多

然而小H经费有限,他想知道最少需要多少糖果。

输入

输入第一行包括一个整数n(1≤n≤105)。 接下来n行,每行1个整数ai(1≤ai≤105)表示站在第i位的人的分数。

输出

输出最少需要多少糖果

样例输入

3
1
2
2

样例输出

4

提示

[提交][状态]