Under construction

Still being built. Things may change

222-Pooling

Interview

Time limit1sMemory limit256 MB

Summary
Repeatedly replace each 2x2 block of an NxN matrix with its second largest value until one number remains, and print it.
Level

Medium4 of 10

Topics
Implementation, Simulation, Divide and conquer, Sorting
Solved
No attempts yet

Problem

Jonguk, who dreams of graduating early, was studying the deep learning that is popular these days. Inspired by the pooling operation of the convolutional neural network (CNN) commonly used in image processing, he invented his own pooling and decided to call it 222-pooling.

The following describes one application of 222-pooling to an 8×8 matrix.

  1. Divide the matrix into 2×2 squares.

  2. Keep only the second largest number in each square. The second largest number means the element a2 when the four elements of the square are ordered by size as a4 ≤ a3 ≤ a2 ≤ a1.

  3. Step 2 reduces the size of the matrix.

Jonguk wonders what value remains when he applies 222-pooling repeatedly to an N×N matrix until its size becomes 1×1.

Mourning Jonguk, whose life has disappeared under the weight of lab work, let us answer his question for him.

Input

The first line gives N (2 ≤ N ≤ 1024). N is always a power of 2. (N=2K, 1 ≤ K ≤ 10)

Each of the next N lines gives the N elements of one row in order. Every entry of the matrix is an integer between -10,000 and 10,000 inclusive.

Output

Print the number that remains at the end.

Hint

For sample 2, the answer is obtained by continuing from the statement as shown below.

Examples2

  1. Example 1

    Input
    4
-6 -8 7 -4
-5 -5 14 11
11 11 -1 -1
4 9 -2 -4
    Expected output
    11

  2. Example 2

    Input
    8
-1 2 14 7 4 -5 8 9
10 6 23 2 -1 -1 7 11
9 3 5 -2 4 4 6 6
7 15 0 8 21 20 6 6
19 8 12 -8 4 5 2 9
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
    Expected output
    17