Hide

Problem I
Maximum Fix

A permutation is a list of integers a1,a2,,an where every number from 1 to n appears exactly once. We can rotate a permutation a1,a2,,an by k to get a new permutation b1,b2,,bn 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 bi=i. Given a1,a2,,an, determine a rotation amount k that maximizes the number of fixed elements.

Input

The first line contains an integer n, where 1n106. The second line contains n space seperated integers describing a permutation a1,a2,,an.

Output

Output two space separated integers k and f, where k is a non-negative integer which maximizes f, the number of fixed elements of b1,b2,,bn. If multiple such k exist, you should output the smallest one.

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

Please log in to submit a solution to this problem

Log in