通过海量题库、编程比赛和实时排名，系统化提升您的编程能力。
如果一个数组A[1...n]中某个元素的数量超过其元素数量的一半，称其包含主元素，假设比较两个 元素大小的时间不是常数但判定两个元素是否相等的时间是常数，要求对于给定数组A，设计时间复杂性为O(nlogn)的算法找到主元素（假设该元素一定存在）。
第一行包含一个整数n（0 < n <= 1000），表示数组大小；第二行包含n个整数，分别是数组中的每个元素（大于-50且小于50），相邻两个元素之间用单个空格隔开。
输出主元素
3 1 2 2
2