CODEM3 - Problem3


 

Arrays are one of the most basic and widely used Data Structures.While Data Structures like stack,queues,linked list etc are often considered as advanced so we will be playing with arrays only at the moment.So let us play a simple game.We play the game as follows: You will be given an array of integers and you can swap any two elements of the given array at a time. Swapping cost is 1 unit. The motive of the game is to append all zeros if present in the arrray to the end while keeping order of its element.

Find the minimum cost to obtain the motive of the game.

Input

First line contains a number T.(no of test cases)
For each test case 2 lines follow,
First line contains size of array, n<=10^6.
Second line contains array elements.(-10^9 <= value of elements <= 10^9)

 

Output

For each test case print on separate line the mimimum cost to obtain the motive.

Example

Input:
3
4
1 3 0 2
4
1 2 3 0
4
1 2 3 5 Output: 1
0
0

Explaination:
For first case swap 0 and 2. so array becomes 1 3 2 0 hence all zeros at the end and order of elements is preserved.(i.e 1 was before 3 , 3 was after 1 and before 2 and so on.)

hide comments
lx_lovin: 2019-08-09 05:29:44

very easy O(1) in average case and O(logn) in worst case
hint : find indexs of all 0's and just swap with next element until next 0 occur

anupam125: 2019-05-15 14:34:39

1
4
0 1 0 1
output of this test case will be 1.

anupam125: 2019-05-15 14:28:24

not getting testcases why my solution is wrong.
provide more test cases.

chunky_2808: 2018-10-04 17:23:50

@suvro_coder output will be 2 as order of element matters
ex 0 1 0 2
we swap 0 and 1( 1 0 0 2) and 0 and 2(1 2 0 0 )

devyash17: 2018-06-13 19:31:29

Last edit: 2018-06-13 19:36:37
suvro_coder: 2018-06-13 18:42:09

@raj its output will be 1!
0101
Swapping first 0 and last 1
1100

coderanant: 2018-05-23 13:15:46

@raj its output is 2

Last edit: 2018-05-23 19:05:56
raj: 2017-12-07 22:12:22

what should be the output of the following testcase ?
1
4
0 1 0 1

Last edit: 2017-12-07 22:12:35
lovedeep_9697: 2017-08-13 20:49:06

please provide us with the testcases

atul_8: 2017-02-15 06:02:12

please provide me with test cases


Added by:Bhavik
Date:2014-02-04
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem(for CODE MARATHON)