3924. 排列变换

【题目描述】

小 x 有一个排列 $p$。小 x 认为，当 $p_i\ge i$ 时，$p_i$ 是一个好数。 

定义 $f(p)$ 表示 $p$ 中的好数数量。 小 x 每次可以将 $p$ 中的最后一个数移到最前面，她想用最少的操作次数使得 $f(p)$ 最大，请找出 $f(p)$ 最大值和使得 $f(p)$ 最大的对应操作次数。

形式化题意. 给定一个 $n$ 阶排列 $p[1:n]$，定义 $f(p)=\sum\limits_{i=1}^n [p_i\ge i]$，求最小的 $x$，使得 $p$ 循环右移 $x$ 位后 $f(p)$ 最大。

当且仅当 $1\sim n$ 中的每个数都在 $p$ 中出现一次，$p$ 被称为一个排列。

【输入格式】

第一行一个整数 $n$，表示排列大小。

第二行有 $n$ 个整数 $p_1\sim p_n$，表示排列 $p$。

【输出格式】

两个整数，分别表示 $f(p)$ 移动后的最大值，和使得 $f(p)$ 最大的位移大小。

【样例输入】

7
1 6 2 5 4 3 7

【样例输出】

5 4

【样例说明】

移动 4 次后，排列变成 $[5, 4, 3, 7, 1, 6, 2]$，其中 $5, 4, 3, 7, 6$ 是好数，故 $f(p)$ 此时为 5.

大样例

【数据规模与约定】

对于 $50\%$ 的数据，满足 $1\le n\le 5000$。

另有 $15\%$ 的数据，满足 $\forall i\in [1,n],p_i=i$。

对于 $100\%$ 的数据，满足 $1\le n\le 10^6$。

【来源】

璃月港算法竞赛 T2.