MAJOR - Majority

The human tribe has just discovered some other tribe and wants to communicate with them. To make sure it is not intercepted by the terminators, they ask their chief computer engineer Rohit to design a system for the purpose. In the design that Rohit proposes, data is transmitted n times. If it is received more than half-the times, it is said to be successfully transmitted. If not, the data is said to be lost. Rohit obviously got a lot of fame and respect for his work. Nitish doesn’t like it and wants to challenge Rohit’s supremacy. He wants to check out the system and has hired you for the process.

Input

The first line of the input contains test cases t (1 <= t <= 100). It is followed by 2*t lines, 2 for each test case. The first line of input for each test case contains a number n (0 <= n <= 106), followed by n elements in the next line. Each number is from -10^3 to +10^3

Output

You are required to output ‘YES’ followed by the number transmitted, if it was transmitted successfully, and ‘NO’ otherwise.

Example

Input:
3
4
2 1 2 2
6
1 1 1 2 2 2
5
1 2 4 5 1

Output:
YES 2
NO
NO

Added by:Troika::Bytes
Date:2010-02-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6

hide comments
2012-12-14 13:50:25 gourav
a very very small trick.. but still need some thinking :-)
2012-07-22 10:43:51 :)
good ques..req. some tricks otherwise TLE..can be solved using cin and cout:):)
2012-07-22 10:43:50 :)
good ques..req. some tricks otherwise TLE..can be solved using cin and cout:):)
2012-07-21 19:42:10 Simón Murillo Gómez
Easy but tricky one.
2012-06-19 04:40:36 BLANKRK
finally AC....
2012-06-15 11:18:43 Darky
good one for starters like me! btw use scanf and printf to avoid TLE.

Last edit: 2012-06-15 11:19:57
2012-05-26 18:46:36 numerix
Python doesn't crash, but algorithm must be well optimized to get AC with Python.
2012-05-26 18:33:17 Shubham
Python crashes whenever there's a loop of a million terms :(
AC in C++ though with same algo
2012-04-23 08:26:26 Amit
how can O(n) give TLE ?
Is there problem with o/p format ?
2012-01-26 21:13:02 Garima Sachan
@Anshul garg @ Ahmed Akram
o/p will be NO bcoz neither 1 or 2 was transmitted >3
Read problem statement and bartender comment..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.