题目内容

在一个大小为 $N \times N$ 的数字方阵中，定义一种「区域归约」操作： 若方阵边长大于 $1$，将其均匀划分为四个边长减半的子方阵。 对每个子方阵递归进行同样的操作，得到四个整数值。 然后取这四个值中第二大的（即升序排序后正数第二个）作为当前方阵的归约结果。 若方阵边长等于 $1$，归约结果即为该位置的元素本身。

现在给定一个初始的 $N \times N$ 数字方阵，请你计算经过上述递归归约后，整个方阵最终得到的数值。

保证方阵边长 $N$ 是 $2$ 的幂，且 $2 \le N \le 1024$。方阵中每个元素的绝对值不超过 $10000$。

输入描述

第一行包含一个整数 $N$，表示方阵的边长。 接下来的 $N$ 行，每行包含 $N$ 个整数，表示方阵对应行的元素。整数之间由空格分隔。

输出描述

输出一个整数，表示整个方阵的最终归约结果。

样例1

输入

2
-10 20
30 -40

输出

20

说明

$2 \times 2$ 矩阵直接划分为四个 $1 \times 1$ 元素：$-10$、$20$、$30$、$-40$。 将这四个数升序排序：$-40, -10, 20, 30$。第二大的数（即倒数第二）为 20，因此归约结果为 20。

样例2

输入

2
-5 10
0 -2

输出

0

说明

$2 \times 2$ 矩阵四个单元素分别为 $-5$、$10$、$0$、$-2$。 升序排序为 $-5, -2, 0, 10$，其中第二大的数是 0，因此归约结果为 0。该样例展示了包含 $0$ 和负数时取第二大的逻辑。

样例3

输入

8
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1

输出

-1

说明

矩阵中所有元素均为 -1。无论方阵边长多大，每次划分得到的四个子方阵归约结果都是 -1，四个 -1 中第二大的数依然是 -1。递归到顶层，最终归约结果仍为 -1。