Optimal Road Placement

You are given n buildings on a 2D plane, each with an entrance at coordinates \((x, y)\). The task is to determine the optimal x-coordinate at which to construct a vertical road such that the total connection length from all building entrances to the road is minimized.

Mathematically, if the x-coordinates of the building entrances are \(x_1, x_2, \dots, x_n\), then the total connection length is given by:

$$\sum_{i=1}^{n}|x_i - m|$$

This expression is minimized when \(m\) is chosen as the median of the x-coordinates. In the case of an even number of buildings, the median is computed as the average of the two middle values, and then rounded to the nearest integer.

inputFormat

The input is read from standard input (stdin).

The first line contains a single integer (n) ((1 \le n \le 10^5)), the number of buildings. Each of the next (n) lines contains two space-separated integers representing the x and y coordinates of a building's entrance. Only the x-coordinate is used for determining the road placement.

outputFormat

Output a single integer to standard output (stdout) representing the optimal x-coordinate for placing the vertical road.## sample

3
1 2
2 3
4 1

2