Sediment Core Majority Mineral Threshold

A geology lab drills a long sediment core and records the mineral code of every sample taken along its length. The n mineral codes are handed to you already sorted in non-decreasing order, exactly as the lab's spectrometer streams them out. The lead geologist suspects that one particular mineral code, target, dominates the core -- meaning it accounts for strictly more than half of all n samples -- and wants this confirmed without scanning the whole core by hand, since a single core can hold hundreds of thousands of readings. Because the list is sorted, every occurrence of target is guaranteed to sit in one contiguous block, so its first and last position can be located with a search that never touches most of the array.

Write a program that reports whether target is a strict-majority code of the core.

Input format

Line 1: a single integer n, the number of samples. Line 2: n integers separated by spaces, the mineral codes in non-decreasing order. Line 3: a single integer target, the mineral code being tested.

Output format

Print true if target occurs strictly more than n / 2 times among the samples, otherwise print false.

Constraints

• 1 <= n <= 10^5
• 1 <= mineral code <= 10^9 for every sample
• 1 <= target <= 10^9
• the samples are given in non-decreasing order

7
2 2 4 4 4 4 6
4

true

5
1 2 3 4 5
3

false