Description
Solutions
Extract Cards

You are given some numbered cards which are a permutation of length n, you have to extract each card in increasing order i.e. 1,2,...n. You are allowed to do 3 types of operations any number of times.

  • Take the first card and put it after the last element, doing this will add the number on the first card to your score.
  • Take the last card and put it before the first position, doing this will add the number on the last card to your score.
  • Discard the card if it's in the correct order (1,2,...n), for free.

    • We want to minimize the final score and print it. Also, the answer can be huge so print the score modulo 1e9+7.

    Example 1: 

    Input:  cards = [3, 5, 1, 4, 2]
    Output: 15 
    Explanation:
    
      
    
      First, we move the last 3 cards numbered 2, 4, 1 using the 2nd operation adding 7 to our score. Then we get the new array as [1,4,2,3,5], now we use the 3rd operation to remove the 1st card, so the new array becomes [4,2,3,5], next we use the 1st operation and shift card number 4 at the last adding 4 to our score, so the new array after this operation [2,3,5,4] and our score is 11.
      
    
      
    
      Next, we remove the card numbered 2 using the 3rd operation, so our new array becomes [3,5,4], and we add 0 to our score. Next, we remove card numbered 3 and add 0 to our score. The new array [5,4], now we apply the 2nd operation to shift card number 4 to the first position and add 4 to our score. New score = 15, now we remove the cards numbered 4 & 5 using the 3rd operation and adding 0 to our score both times. So the final score = 15.
    Constraints:
      • 1 ≤ n ≤ 10^5
      • 1 ≤ Arr[i] ≤ n
    Thumbnail 0
    Testcase
    Result
    Case 1

    input:

    output: