Background

土拨鼠的松果难题​

Description

深秋的森林里，土拨鼠正在为冬眠储备松果。它在不同的松树下收集了一堆堆松果，每堆松果都有不同的大小 —— 有的是饱满的大松果（记为 3），有的是中等大小的松果（记为 2），还有的是小巧的松果（记为 1）。​ 土拨鼠发现，今年有一种松果特别多，数量超过了所有松果总数的一半。这种松果将成为它冬眠时的主要食物来源，必须优先整理出来。​ 现在，土拨鼠的洞穴里堆着一排松果，每个松果都用数字 1、2、3 标记大小。请你帮阿栗找出这种数量占绝对优势的松果（即出现次数大于总数一半的那个数字）。​

Samples

3 2 3

3

Limitation

1s, 1024KiB for each test case. 设计时间复杂度为 O (n)、空间复杂度为 O (1) 的算法​ 使用 C++ 实现该算法