← 返回题目列表

Codeforces · 1220/F

F. 园丁亚历克斯

中文机器翻译题面 查看原题

园丁亚历克斯喜欢种树。我们提醒一下,树是 $$$n$$$ 个顶点上的连通无环图。

今天他决定种植一棵有根二叉树。二叉树是任意顶点的儿子数不超过两个的树。幸运的是,Alex 有一个从 $$$1$$$ 到 $$$n$$$ 的数字排列,这是他在上一个生日时收到的,所以他决定根据这个排列种植一棵树。为此,他执行以下过程:找到一个最小元素并将其作为树的根。之后,排列分为两部分:最小元素左侧的所有内容和右侧的所有内容。左边部分的最小元素成为根的左子元素,右边部分的最小元素成为根的右子元素。之后,在两个部分上递归地重复此过程。

现在 Alex 想要种植一片树木:排列的每个循环移位对应一棵树。他感兴趣的是循环移位如何赋予树最小深度。不幸的是,种植森林是一个艰难而漫长的过程,但亚历克斯现在就想得到答案。你会帮助他吗?

我们提醒一下,$$$k$$$元素的排列$$$a_1, a_2, \ldots, a_k, \ldots, a_n$$$向左循环移位是排列$$$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$$$ 的数字。如果有多个可能的答案,请打印其中任何一个。

示例

输入 #1

4
1 2 3 4

输出 #1

3 3

注意

下图描述了用于样本测试的所有可能的树以及实现它们的循环移位。