Dare2Compete sample question-2

How to approach this problem?


Avi likes integer sequences. His parents gave him a birthday gift that is an integer sequence of length n containing integers from 1 to n.

Let’s denote the sequence by p1, p2, p3, … pn, where p1, p2, …pn consist of 1, 2, 3, 4, … n in any order.

Now Avi does not like a sequence if for any index in the sequence the index and the value at the index in sequence are equal, that is pi = i.

He wants to form a new sequence that satisfies the property that for any index i, pi != i, using the following operation minimum number of times.

Operation: Swap two adjacent elements in the sequence.

1 <= n <= 100000
1 <= pi <= n

Input Format:
The first contains an integer n
The second line contains n integers, from 1 to n in any order.

Output Format
The output should contain one line denoting the minimum required number of operations to achieve

Thanks in advance!

1 Like