Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • 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.
     
    notion image
    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

    1. Go from the 1st plant to the 2nd ⇒ 1 minute
    1. Water the 2nd plant ⇒ 1 minute ⇒ 3 2 5 6 2 5
    1. Go from the 2nd plant to the 5th ⇒ 3 minutes
    1. Water the 5th plant ⇒ 1 minute ⇒ 3 2 5 6 2 5
    1. Go from the 5th plant to the 1st ⇒ 4 minutes
    1. Water the 1st plant ⇒ 1 minute3 2 5 6 2 5
    1. Go from the 1st plant to the 3rd ⇒ 2 minutes
    1. Water the 3rd plant ⇒ 1 minute3 2 5 6 2 5
    1. Go from the 3rd plant to the 6th ⇒ 3 minutes
    1. Water the 6th plant ⇒ 1 minute3 2 5 6 2 5
    1. Go from the 6th plant to the 4th ⇒ 2 minutes
    1. Water the 4th plant ⇒ 1 minute3 2 5 6 2 5
    In total → 1 + 1 + 3 + 1 + 4 + 1 + 2 + 1 + 3 + 1 + 2 + 1 = 21
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue