MAJOR - Majority

no tags 

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

hide comments
nadstratosfer: 2017-12-27 03:07:04

Simple problem but many oportunities to optimize the code. From TLE to 0.27s to 0.18s in PyPy in several steps, each time taking a chance on something I didn't expect to matter, yet always yielding a tangible improvement.

mpride44: 2017-12-26 21:51:05

ac in 1 go...simple moore voting algo..

shauryauppal: 2017-11-28 21:32:39

Method1
MAP is hashing Logic O(n).

Method2:
Use Moore's voting Algorithm Logic O(n).

ayushgupta1997: 2017-10-18 06:23:42

Piece of cake--naive way to use map :) Use Moore voting to learn something new

dinkar: 2017-09-25 12:35:01

Why does it give wrong answer if I do not read input completely.
If I start processing elements as they arrive and not store them in an array, I get WA.

karthik1997: 2017-08-29 22:36:53

Woo fast i/o 0.00s and scanf,printf - 0.50s

viratian_070: 2017-06-28 11:18:24

a simple problem to show that scanf printf can create a diff

sandeep_4141: 2017-05-17 18:43:37

AC one go !! Moore's voting algo ,with scanf & printf in cpp !!

rohit9934: 2017-05-07 17:50:57

IF you are using boyre moore voting algo in c++. use Fast I/O technique to vaccinated from TLE

prabodh prakash: 2017-05-04 10:18:48

trying to take very fast input costed me three WA ! - simple scanf and printf worked.


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