Thanos排序是一种超级恶棍排序算法,其工作原理如下:如果数组未排序,则打响指*删除前半部分或后半部分的项目,然后重复该过程。
给定一个输入数组,使用 Thanos 排序可以从中获得的最长排序数组的大小是多少?
*需要无限手套。
输入
输入的第一行包含一个数字 $$$n$$$ ($$$1 \le n \le 16$$$) — 数组的大小。 $$$n$$$ 保证是 2 的幂。
输入的第二行包含 $$$n$$$ 空格分隔的整数 $$$a_i$$$ ($$$1 \le a_i \le 100$$$) — 数组的元素。
输出
返回使用 Thanos 排序可以获得的排序数组的最大长度。数组的元素必须按非降序排序。
示例
输入 #1
4 1 2 2 4
输出 #1
4
输入 #2
8 11 12 1 2 13 14 3 4
输出 #2
2
输入 #3
4 7 6 5 4
输出 #3
1
注意
在第一个示例中,数组已经排序,因此不需要进行手指捕捉。
在第二个示例中,数组实际上有一个包含 4 个已排序元素的子数组,但您无法快速删除数组不同侧的元素。每次您都必须删除整个前半部分或整个后半部分,因此您必须打响指两次才能获得 2 元素排序数组。
在第三个示例中,数组按降序排序,因此您只能保存一个元素免遭最终破坏。