No tags yet

No tag edit access

Time limit per test: 1 second(s)

Memory limit: 262144 kilobytes

Memory limit: 262144 kilobytes

input: standard

output: standard

output: standard

You are employed to implement a new fast sorting algorithm called multiswap sorting. The basic idea is simultaneous execution of multiple parallel swaps. You are given an array containing

For example, you are given the array [5, 4, 3, 2, 1]. At one step you can select two pairs (5, 1) and (4, 2), swap elements in them and get the array 1, 2, 3, 4, 5. Pairs (1, 2) and (2, 3) cannot be selected at one step, because they have the common element 2. So it is possible to sort the array [5, 4, 3, 2, 1] in one step.

Sort the given array in the minimum possible number of steps carrying out selection of pairs at each step optimally. Note that you are not required to minimize the total number of single swaps but the number of steps.

sample input | sample output |

3 1 2 3 | 0 |

sample input | sample output |

5 5 4 3 2 1 | 1 2 1 5 2 4 |

sample input | sample output |

4 3 1 2 2 | 2 2 1 2 3 4 1 4 2 |

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/19/2019 08:24:20 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|