Help in solving below problem. I am unable to solve this problem.

Therasa is a Nurse. She wants to give some tablets to the patients in her practice. All the patients sit in a line and each of them has a rating score according to his or her health score. Therasa wants to give at least 1 tablet for each patient. Patients get jealous of their immediate neighbors, so if two patients sit next to each other then the one with the higher rating must get more tablets. Therasa wants to save money, so she wants to minimize the total number of tablets.

Input

The first line of the input is an integer N, the number of patients in Therasa’s practice. Each of the following N lines contains an integer indicates the health score of each patient.

Output

Output a single line containing the minimum number of tablets Therasa must give.

Constraints

1 <= N <= 100000

1 <= health score <= 100000

link to problem