← 返回题目列表

Codeforces · 1145/A

A. 灭霸排序

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

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 元素排序数组。

在第三个示例中,数组按降序排序,因此您只能保存一个元素免遭最终破坏。