A new rollercoaster has opened nearby and everyone is keen to see it$.$ Unfortunately, it also has a long queue. Some people are bribing those in front to move more quickly through the queue. You want to identify how many bribes have taken place.

You wait until the ride is stopped for maintenance and record the position of all people in the line. You record the positions of everyone in the queue, giving everyone a number from $1$ to N$,$ where person $1$ is at the front of the queue, person N is at the back. Any person can swap positions with the person in front of them, and only the person in front of them, $($for a small bribe$).$ Someone could move all the way through the queue by bribing multiple times. During this period no$-$one leaves or joins the queue. After the maintenance finishes you again record the positions of everyone, which may now be jumbled up if bribes have taken place.

You have to figure out what is the smallest number if bribes that could have happened to produce a given queue order.

For example:

If the initial state of the queue is $[1,2,3,4,5,6],$ and the new state is $[1,2,3,6,4,5],$ then person $6$ has paid two bribes and you should return $2.$

If the initial state of the queue is $[1,2,3,4,5,6],$ and the new state is $[2,1,4,3,6,5],$ then persons $2,4$ and $6$ have each bribed the person in front and you should return $3.$

If the initial state of the queue is $[1,2,3,4,5,6],$ and the new state is $[6,5,4,3,2,1],$ then person $6$ made $5$ bribes to get to the front, person $5$ made $4$ bribes to get in front of $1,2,3$ and $4,$ person $4$ made $3$ bribes etc. and so you should return $15.$

The queue can be very long, and may have as many as $10000$ people in it$.$

WARNING

As with the Sums question, this question can time out the server if your code is not efficient. Here we have not provided a default timeout condition. You may need to implement one here to pass the shorter test cases before attempting the long ones!