Problem I
Maximum Fix

A permutation is a list of integers $a_1,a_2,\dots ,a_ n$ where every number from $1$ to $n$ appears exactly once. We can rotate a permutation $a_1,a_2,\dots ,a_ n$ by $k$ to get a new permutation $b_1,b_2,\dots ,b_ n$ by moving the first $k$ elements to the end. For example, rotating the permutation $1,3,5,2,4$ by $3$ yields $2,4,1,3,5$. We say that $i$ is fixed if $b_ i=i$. Given $a_1,a_2,\dots ,a_ n$, determine a rotation amount $k$ that maximizes the number of fixed elements.


The first line contains an integer $n$, where $1\le n\le 10^6$. The second line contains $n$ space seperated integers describing a permutation $a_1,a_2,\dots ,a_ n$.


Output two space separated integers $k$ and $f$, where $k$ is a non-negative integer which maximizes $f$, the number of fixed elements of $b_1,b_2,\dots ,b_ n$. If multiple such $k$ exist, you should output the smallest one.

Sample Input 1 Sample Output 1
5 1 2 3 4
1 5
Sample Input 2 Sample Output 2
11 3 8 7 1 2 9 4 5 6 10
4 5

Please log in to submit a solution to this problem

Log in