Points:
1700 (p)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Here are some possible methods using which we can sort the elements of an array in increasing order:
- At each step, choose two adjacent elements and swap them.
- At each step, choose any two elements and swap them.
- At each step, choose any element and move it to another position.
- At each step, choose any element and move it to the front of the array.
Given a permutation of numbers \(1,2,…,n\), calculate the minimum number of steps to sort the array using the above methods.
Input
- The first input line contains an integer \(n\).
- The second line contains \(n\) integers describing the permutation.
Output
- Print four numbers: the minimum number of steps using each method.
Constraints
- \(1\leq n \leq 2 ⋅ 10^5\)
Example
Sample input
8
7 8 2 6 5 1 3 4
Sample output
20 6 5 6
Comments
Dưới đây là một số phương pháp có thể sử dụng mà chúng ta có thể sắp xếp các phần tử của một mảng theo thứ tự tăng dần:
Cho một hoán vị của các số \(1,2,…,n\), hãy tính số bước tối thiểu để sắp xếp mảng bằng các phương pháp trên.
Input
Output
Test 1
Input
Output