Minimum Meeting Height

You are given a list of non‐negative integers representing the heights of buildings along a street. Two persons start at the two ends of the list and move towards each other. At each step, the person standing at the lower building moves one step inward, and the meeting height is updated to be the minimum of the encountered building heights. The process continues until the two persons meet. Your task is to compute the minimum height encountered during their journey.

More formally, let \(H[0 \ldots n-1]\) be the list of building heights. Initialize two pointers \(i = 0\) and \(j = n-1\), and let \(m = \min(H[0], H[n-1])\). While \(i < j\), if \(H[i] < H[j]\) then increment \(i\) and update \(m = \min(m, H[i])\); otherwise, decrement \(j\) and update \(m = \min(m, H[j])\). Output \(m\) as the minimum height encountered.

Note: If there is only one building, then the answer is simply its height.

inputFormat

The input is read from standard input. The first line contains an integer \(n\) representing the number of buildings. The second line contains \(n\) space-separated integers representing the building heights.

Example:

8
5 3 6 4 2 4 1 2

outputFormat

Output a single integer to standard output — the minimum height encountered as the two persons progress towards each other.

Example:

1

## sample

8
5 3 6 4 2 4 1 2

1