Description

Every year on 1024 Programmer Day, Heima Programmer holds a large celebration event. This year is no exception, and every student in each class received oranges.

There are $n$ students in the class standing in a line from front to back, and their scores are known. The score of the $i$-th student is $a_i$. The head teacher wants to decide how many oranges to give based on the students' exam scores from the previous stage. To encourage students with better scores, the distribution of oranges must satisfy the following rules:

• For any two adjacent students, the one with the higher score must receive more oranges. If two adjacent students have the same score, they must receive the same number of oranges.
• Each student must receive at least one orange.

Due to a limited budget, the head teacher wants to give out as few oranges as possible while meeting the rules. How many oranges need to be prepared at minimum?

Input Format

The first line contains an integer $n$, representing the number of students.

The next line contains $n$ integers. The $i$-th integer $a_i$ represents the score of the $i$-th student.

Output Format

Output the answer, i.e., the minimum total number of oranges that need to be prepared.

5
3 4 5 4 3

9

Hint

Explanation for Sample 1

The numbers of oranges received by each student are $1,2,3,2,1$, so at least $9$ oranges are needed.

Constraints

For all testdata, it is guaranteed that $1 \leq n \leq 10^6$ and $0 \leq a_i \leq 10^9$.

Translated by ChatGPT 5