Description

n个小朋友玩游戏，游戏结束之后每个小朋友有一个得分。
小朋友站成一排，你现在要给小朋友发糖。
你需要保证
1.每个小朋友至少有一颗糖
2.如果一个小朋友比他左右两边相邻的小朋友中的某一个分数更高，那么他所被分到的糖也要比他更多一点（至少多一个）
求能够满足条件的最少的话费糖的个数

Input

第一行一个正整数n（1<=n<=100000）
第二行n个正整数表示每个小朋友的得分ai（ai<=100000）

Output

一个正整数，即需要花费的糖的最小个数

Sample 1

Input

3
5 3 5

Output

5

Sample 2

Input

5
30463 20623 28773 26377 11672

Output

9

Limitation

1s, 64Mb for each test case.

Hint

Free Pascal Code

var a,b:longint;
begin
    readln(a,b);
    writeln(a+b);
end.

C Code

#include <stdio.h>
int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
}

C++ Code

#include <iostream>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
    return 0;
}

Python Code

a, b = [int(i) for i in raw_input().split()]
print(a + b)

Java Code

import java.io.*;
import java.util.Scanner;

public class Main {

    /**
     * @param args
     * @throws IOException 
     */
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println(a + b);
    }
}

Source

Vijos Original