#O3816. LQ.蓝桥杯.十四届.国赛.编程题.02.主要成分

LQ.蓝桥杯.十四届.国赛.编程题.02.主要成分

背景信息

金星是离地球最近的行星,人类发射的“金星快车”探测器的主要任务是对金星大气层进行精确的探测,分析其化学成分。

问题描述

从金星探测器传回来一组测量数据,这是一个长度为 N( 1N<106 )N(\ 1 \le N \lt 10^6\ ) 的整数数列,数列中的每个整数代表某一种化学成分(相同的整数代表相同的化学成分)。

主要成分:指在包含的所有化学成分中比例超过一半(N÷2N \div 2 的结果向下取整)的成分。

现在要判断其是否有主要成分;如果有,其主要成分是哪一种?

例如:

N=7N=7 ,整数数列为 1 2 3 2 2 1 2, 其中成分 2 有 4 个,超过了 7 的一半( 7 的一半向下取整为 3 ),所以主要成分是 2 。

N=6N=6,整数数列为 1 102 31 31 1 102, 其中的每一种成分都只有 2 个,未超过 6 的一半(6 的一半为 3 ),所以没有主要成分。

输入描述

第一行输入一个正整数N( 1N<106 )N(\ 1 \le N \lt 10^6\ ),表示数列长度

第二行输入NN 个整数( 11 \le 整数 2109\le 2*10^9 ),每个整数表示一种化学成分,两个整数之间用一个空格隔开

输出描述

输出一行,如果存在主要成分,则输出代表主要成分的整数,否则,输出 NO

样例

7
1 2 3 2 2 1 2
2