All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Tablets
/

Dynamic Programming

Problem
Editorial
Analytics

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

SAMPLE INPUT
3
1
2
2
SAMPLE OUTPUT
4
Explanation

Here 1, 2, 2 is the health score. Note that when two patients have equal health score they are allowed to have different number of tablets. Hence optimal distribution will be 1, 2, 1.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?