CF1220F Gardener Alex

园丁 Alex 喜欢种树。树是一个包含 $n$ 个顶点的连通无环图。 今天他决定种一棵有根二叉树。二叉树是指任意一个顶点的儿子不超过两个的树。幸运的是，Alex 拥有一个从 $1$ 到 $n$ 的排列，这是他上次生日时收到的礼物，所以他决定按照这个排列来种树。具体过程如下：他找到排列中的最小元素，并将其作为树的根节点。然后将排列分为两部分：最小元素左边的所有元素和右边的所有元素。左边部分的最小元素作为根的左儿子，右边部分的最小元素作为根的右儿子。之后，对这两部分递归重复上述过程。 现在 Alex 想要种一片森林：对于排列的每一个循环左移，都种一棵树。他想知道，哪一种循环左移能使树的深度最小。不幸的是，种一片森林既困难又耗时，但 Alex 现在就想知道答案。你能帮帮他吗？ 对于排列 $a_1, a_2, \ldots, a_k, \ldots, a_n$，循环左移 $k$ 位后的排列为 $a_{k+1}, a_{k+2}, \ldots, a_n, a_1, a_2, \ldots, a_k$。

第一行包含一个整数 $n~(1 \leqslant n \leqslant 200\,000)$，表示排列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n~(1 \leqslant a_i \leqslant n)$，保证所有数字恰好出现一次。

输出两个用空格分隔的整数：树的最小可能深度，以及需要左移多少个元素才能达到这个深度。左移的元素个数应为 $0$ 到 $n-1$ 之间的一个数。如果有多组答案，输出任意一组即可。

下图展示了样例测试中所有可能的树以及它们对应的循环左移次数。  由 ChatGPT 4.1 翻译