Minimum Rewards Distribution

In this problem, you are given M employees, each with an integer rating. Your task is to determine the minimum number of rewards you must distribute such that each employee receives at least one reward and any employee with a higher rating than an adjacent employee receives more rewards than that neighbor.

You can think of it as a variation of the candy problem. One effective approach is to use two passes: one from left to right and another from right to left, ensuring the reward conditions are satisfied in both directions.

Formally, let \( r_1, r_2, \dots, r_M \) be the ratings. You must assign rewards \( a_1, a_2, \dots, a_M \) such that:

• \( a_i \ge 1 \) for all \( i \), and
• If \( r_i > r_{i-1} \) then \( a_i > a_{i-1} \), and if \( r_i > r_{i+1} \) then \( a_i > a_{i+1} \).

Your goal is to minimize \( \sum_{i=1}^{M} a_i \).

inputFormat

The input is read from standard input and consists of two lines:

1. The first line contains a single integer M representing the number of employees.
2. The second line contains M space-separated integers, representing the ratings of the employees.

outputFormat

Output a single integer representing the minimum total number of rewards required. Print the answer to standard output.

5
1 2 2 3 1

7