Elements Appearing More Than n/3 Times

Given an array of n integers, find every distinct value that appears strictly more than floor(n/3) times. There can be at most two such values in any array. Report them in increasing order; if no value satisfies the condition, report that none exists. Solve it in a single pass with O(1) extra space using an extended voting-based search technique (tracking two running candidates instead of one), followed by a verification pass.

Input: The first line contains the integer n. The second line contains n space-separated integers, the array. Output: Print the qualifying values in increasing order, space-separated, on one line. If no value qualifies, print "NONE".

1 <= n <= 10^5 -10^9 <= a[i] <= 10^9

Unlike the simpler >n/2 majority problem (where existence is often guaranteed, skipping verification), THIS problem's threshold doesn't guarantee ANY value clears it - the verification pass is not optional here, it's essential to avoid falsely reporting a candidate that didn't actually meet the threshold.

Find every value appearing more than n/3 times in an array, using an extended voting technique with two running candidates. Brute force: Use a hash map to count every value's occurrences directly - this works but costs O(n) extra space, when the extended voting technique achieves the same result in O(1) space. Optimised: Since at most TWO values can ever exceed the n/3 threshold simultaneously (three values each appearing more than n/3 times would together exceed n, which is impossible), tracking exactly two running candidates (rather than just one, as in the simpler >n/2 majority problem) with the same cancellation logic finds both POTENTIAL answers in one pass - a mandatory verification pass then confirms which candidates are genuinely valid, since (unlike the guaranteed-majority problem) this problem doesn't guarantee either candidate is real.

1. Track up to TWO running candidates and TWO counters simultaneously (a single-candidate vote only works for the >n/2 threshold). 2. When neither current candidate matches the new value AND both counters are already positive, DECREMENT both counters instead of replacing a candidate. 3. The two candidates surviving this pass are only POTENTIAL answers - re-scan the array to count their REAL occurrences and confirm each one actually exceeds floor(n/3) before reporting it.

Time: O(n) - one voting pass plus one verification pass, both linear. Space: O(1) - two candidates and two counters, no hash map needed.

n = 1 (the single element trivially exceeds floor(1/3) = 0 occurrences); arrays where no value exceeds the threshold at all.

Be ready to explain WHY at most two values can ever exceed n/3 simultaneously - this counting argument (three such values would together exceed n) is exactly what justifies tracking only two candidates, not three or more.