Employee Bonuses Distribution

You are given an array of integers, where each integer represents the rating of an employee. Your task is to determine the minimum number of bonuses required such that:

• Every employee receives at least one bonus.
• If an employee has a higher rating than an immediate neighbor, then they must receive more bonuses than that neighbor.

The problem can be formalized as follows. Let \(b_i\) be the bonus for the \(i^{th}\) employee and \(r_i\) be their rating. Then: \[ \begin{aligned} &b_i \ge 1,\\ &\text{if } r_i > r_{i-1}, \text{ then } b_i > b_{i-1},\\ &\text{if } r_i > r_{i+1}, \text{ then } b_i > b_{i+1}. \end{aligned} \]

Your program should process multiple test cases and output the sum of the bonuses for each test case.

inputFormat

The input is read from stdin and consists of multiple test cases. Each test case has the following format:

n
r1 r2 r3 ... rn

Where n represents the number of employees and r1, r2, ..., rn are the space-separated integer ratings of the employees. The input ends with a test case where n is 0, which should not be processed.

outputFormat

For each test case, output a single line to stdout containing the minimum total number of bonuses required.

3
1 2 2
0

4