Submajority Vote

You are given a list of integers nums where each number represents a vote to a candidate.

Return the ids of the candidates that have greater than \(\lfloor \frac{n}{3}\rfloor\) votes, in ascending order.

Bonus: solve in \(\mathcal{O}(1)\) space.

Constraints

• n ≤ 100,000 where n is the length of nums.

https://binarysearch.com/problems/Submajority-Vote

Examples

Example 1

Input

• nums = [1, 1, 1, 1, 2, 3]

Output

• answer = [1]

Example 2

Input

• nums = [2, 1, 5, 5, 5, 5, 6, 6, 6, 6, 6]

Output

• answer = [5, 6]

Explanation

Both 5 and 6 have 40% of the votes.

Solution