Candy Distribution

Problem statement

A mentor distributes reward tokens to learners standing in a row. Everyone needs at least one token. Whenever a learner has a higher rating than an immediate neighbour, that learner must receive more tokens than that neighbour. Find the smallest possible total.

Input format

First line: n. Second line: n space-separated integers.

Output format

Print the minimum total number of tokens.

Constraints

1 <= n <= 50000; 0 <= rating <= 50000.

Sample input

5
1 3 2 2 1

Sample output

7