An assembly line scans a part code into each of n slots. A part code is called dominant if it appears in strictly more than half of the slots (that is, more than n/2 times). At most one value can ever be dominant.
Report the dominant part code if one exists, otherwise report NONE. The intended approach splits the slots into two halves, finds the dominant code of each half recursively, and reconciles the two candidates by counting occurrences across the whole range.
Input format
Line 1: an integer n, the number of slots.
Line 2: n space-separated integers, the scanned part codes in order.
Output format
A single line: the dominant part code, or the word NONE if no value occupies strictly more than half the slots.
Constraints
- 1 <= n <= 100000
- 0 <= each part code <= 1000000000