Yet Another Paper


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

Farshid loves to write scientific papers, even if there is nothing to write paper about. In one of his latest papers he introduced a new sorting algorithm called FS-Sort. In this sort only one operation is available and that is you can swap two adjacent numbers. If you think for a while, you will see that it is always possible to sort any array of numbers in this way. An array of integers will be given. Now using the above approach he wants to sort the numbers in the ascending order. You have to help him find out the minimum number of operations required. For example, to sort ‘1 2 3’ we need no operation. However sorting ‘2 3 1’ requires at least 2 operations.

ورودی🔗

The first line of the input contains a positive integer NN. In next line there will be NN space separated integers denoting the elements of the array.

1N20001 \leq N \leq 2000

خروجی🔗

Print the minimum swap operations required to perform sorting.

مثال‌ها🔗

ورودی نمونه ۱🔗

3
1 2 3
Plain text

خروجی نمونه ۱🔗

0
Plain text

ورودی نمونه ۲🔗

3
2 3 1
Plain text

خروجی نمونه ۲🔗

2
Plain text
  • First you should swap 1 with 3.
  • Then you should swap 1 with 2.

ورودی نمونه ۳🔗

3
2 2 2
Plain text

خروجی نمونه ۳🔗

0
Plain text