You are given a permutation of N numbers from 1 to N in an array

You want to sort the array using this operation

- Send the front-most element X places back in the array;
- Add x to the total cost.

N<=10^5

Input : A = { 1 , 3 , 2 }

output : 3.

Explanation :

=> Send 1 to index 1. (Cost +1)

A [3, 1, 2]

Send 3 to index 2. (Cost +2)

A = [1, 2, 3]

and the array is sorted.

hence total cost = 3.

Any approach for solving this problem>

Welcome to FAKEFORCES

Problem matters.

First, find the largest suffix of the permutation that is in increasing order. For example for the array

`3 6 5 1 2 4 7`

, the largest such suffix will be`1 2 4 7`

. Then we need to place only the elements`3 6 5`

at their correct positions and the array will be sorted after that. For calculating the cost of shifting the element from`3 6 5`

, we can find the number of jumps we need to make in the sorted suffix plus the number of elements that are remaining in the`3 6 5`

part. Say we placed 3 at its correct position. Now the cost will be`2 + 2`

, 2 moves for going beyond`6 5`

and 2 again for going beyond`1 2`

. To calculate the latter we can use`lower_bound`

on`1 2 4 7`

. Now we want to place 6 in the correct position. To calculate moves we can either modify our suffix`1 2 4 7`

, i.e. insert 3 in it and then repeat the same procedure or we can just add the number of elements before`6`

which are less than`6`

in the part`3 6 5`

, which can be done efficiently using Fenwick Tree or Segment Tree.If you find any counter test then please inform.

Yeah, this is correct

what will you do in this case.

3 6 10 5 8 9 11 1 2 4 7

which suffix to take in this condition we we can have same suffix length at various positions.

You can just take last element that $$$a{_i}$$$ < $$$a{_{i-1}}$$$ and the starting position would be $$$i$$$