Dominant Calibration Reading

A lab technician exports a log of n integer calibration readings from a sensor, sorted in non-decreasing order. It is known that exactly one reading value occurs strictly more than 25% of the time (that is, its count is strictly greater than n / 4), while every other distinct value occurs at most n / 4 times. Because the log is huge, the technician wants a program that identifies this dominant reading quickly by taking advantage of the fact that the log is already sorted.

Given the sorted log, report the dominant reading value.

Input format

• Line 1: an integer n
• Line 2: n space-separated integers a[0..n-1] in non-decreasing order

Output format

• A single integer: the value that occurs strictly more than n / 4 times in the log.

Constraints

• 1 <= n <= 10^4
• -10^9 <= a[i] <= 10^9
• a is sorted in non-decreasing order
• Exactly one value in a occurs strictly more than n / 4 times

9
1 2 2 6 6 6 6 7 10

6

6
1 1 1 2 3 4

1