题目描述

晨晨学校需从 $n \times n$ 的学生队列中挑选学生代表，选拔规则如下：

1. 首先，让每一行的同学找出本行的"中间位置学生"。该位置的定义为：行内有一半同学的德育操行分 $\ge$ 该学生的分数，同时有一半同学的分数 $\le$ 该学生的分数（因 $n$ 为奇数，排序后正中间的元素即为该行的中间位置学生）。

2. 收集所有行的"中间位置学生"的操行分，在这些分数中再次找出"中间位置"的分数，对应的学生即为最终的学生代表。

现给出 $n \times n$ 的学生操行分队列（操行分 $r$ 满足 $1 \le r \le 1000$），请计算学生代表的操行分数。

输入格式

第一行输入一个整数 $n$，$n$ 为奇数，表示学生队列的行数（或列数）。

接下来 $n$ 行，每行输入 $n$ 个整数，依次表示该行每个学生的德育操行分，整数之间用空格隔开。

输出格式

输出一个整数，即最终学生代表的操行分数。

样例

5
1 5 3 9 5
2 5 3 8 1
6 3 5 9 2
8 8 3 3 2
5 4 4 4 4

4

提示

选拔过程分两步：

1. 第一步：计算每一行的中间位置分数

   • 第 $1$ 行排序后：$1, 3, 5, 5, 9$，中间位置为 $5$
   • 第 $2$ 行排序后：$1, 2, 3, 5, 8$，中间位置为 $3$
   • 第 $3$ 行排序后：$2, 3, 5, 6, 9$，中间位置为 $5$
   • 第 $4$ 行排序后：$2, 3, 3, 8, 8$，中间位置为 $3$
   • 第 $5$ 行排序后：$4, 4, 4, 4, 5$，中间位置为 $4$
   • 收集每行中间分数：$[5, 3, 5, 3, 4]$

2. 第二步：计算中间分数列表的中间位置

   • 排序后：$[3, 3, 4, 5, 5]$，中间位置为 $4$

数据范围

• $2 \le n \le 99$，且 $n$ 为奇数
• $1 \le r \le 1000$