Take care of your garden
You have a large garden with many plants. Each of those plants requires to be watered. You have been away for the weekend, so you’d like to water all the plants as quickly as possible. But as it takes time, you’ve decided to water plants that have low humidity first.
Everything in the garden is planted in a long row, so moving from one plant to its neighbor takes 1 minute, and watering one plant also takes 1 minute.
Knowing the humidity levels for each of the plants, you’re wondering how many minutes it would take to water all the plants. You’re initially near the first plant.
Input
The first line of the input contains a single integer
n (1 ≤ n ≤ ).The next line contains
n space-separated integers (1 ≤ ≤ n) the humidity levels for each plant.Output
The program should print the number of minutes it would take you to water all the plants.
Examples
Input | Output |
6
3 2 5 6 2 5 | 21 |
Explanation
- Go from the 1st plant to the 2nd ⇒ 1 minute
- Water the 2nd plant ⇒ 1 minute ⇒ 3 2 5 6 2 5
- Go from the 2nd plant to the 5th ⇒ 3 minutes
- Water the 5th plant ⇒ 1 minute ⇒ 3 2 5 6 2 5
- Go from the 5th plant to the 1st ⇒ 4 minutes
- Water the 1st plant ⇒ 1 minute ⇒ 3 2 5 6 2 5
- Go from the 1st plant to the 3rd ⇒ 2 minutes
- Water the 3rd plant ⇒ 1 minute ⇒ 3 2 5 6 2 5
- Go from the 3rd plant to the 6th ⇒ 3 minutes
- Water the 6th plant ⇒ 1 minute ⇒ 3 2 5 6 2 5
- Go from the 6th plant to the 4th ⇒ 2 minutes
- Water the 4th plant ⇒ 1 minute ⇒ 3 2 5 6 2 5
In total → 1 + 1 + 3 + 1 + 4 + 1 + 2 + 1 + 3 + 1 + 2 + 1 = 21
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB