Chef and his Best Friend

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef and Chhotu are best friends. Chef knows that Chhotu is very intelligent. So, Chef gives Chhotu a simple problem and wants him to solve this problem by today. The problem is as follows.
There are N students in a classroom. The students are sitting in a single row. Chef wants that all the girls should sit in left side of the row and all the boys should sit in right side of the row. You are provided the initial row of the students by N binary integers, where if ith integer is zero, then it means that at the ith position, there is a boy, where 1 will mean girl. For example, if the initial arrangement be [0 1 0 1 1], then final arrangement should be [1 1 1 0 0].
In a single second, if a boy finds that a girl is sitting to his immediate right i.e. if a boy is sitting at i^{th} position and a girl is sitting at (i+1)^{th} position then they swap their positions. For example, let the initial arrangement be [0 1 0 1 1]. Boys are sitting at positions 1, 3 (1based indexing) and girls are sitting at positions 2, 4, 5. In a single second, boy at position 1 swaps his seat with girl at position 2, and similarly boy at position 3 swaps his seat with girl at position 4. So, after one second, the arrangement becomes [1 0 1 0 1].
For detailed explanation, please see the explanation of the sample provided at the end of this statement.Now Chef wants to determine the total time after which all the girls move to the left side of the row and all the boys towards the right side of the row.Chhotu can solve this problem very easily but today he is very busy. Please help Chhotu to solve this problem.
Input
The first line of the input contains T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains an integer N denoting the number of students in the row.
The second line contains N spaceseparated integers  A_{1}, A_{2}, ..., A_{N }denoting the initial arrangement of the students.
Output
For each test case, output a single integer on a new line corresponding to the number of seconds required such that all girls are to the left of boys.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 10^{5}
 0 ≤ A_{i } ≤ 1
Subtasks
Subtask #1 (30 points):
 1 ≤ T ≤ 10
 1 ≤ N ≤ 10^{3}
Subtask #2 (70 points):
 1 ≤ T ≤ 10
 1 ≤ N ≤ 10^{5}
Example
Input:
2 10 0 1 1 1 0 1 1 0 1 1 5 0 1 0 1 1
Output:
7 3
Explanation
Test case 1:
Initially, student's arrangement is [0 1 1 1 0 1 1 0 1 1]
After1^{st} second [1 0 1 1 1 0 1 1 0 1]
After 2^{nd} second [1 1 0 1 1 1 0 1 1 0]
After 3^{rd} second [1 1 1 0 1 1 1 0 1 0]
After 4^{th} second [1 1 1 1 0 1 1 1 0 0]
After 5^{th} second [1 1 1 1 1 0 1 1 0 0]
After 6^{th} second [1 1 1 1 1 1 0 1 0 0]
After 7^{th} second [1 1 1 1 1 1 1 0 0 0]
Total time taken = 7 seconds
Test case 2:
Initially, student's arrangement is [0 1 0 1 1]
After 1^{st} second [1 0 1 0 1]
After 2^{nd} second [1 1 0 1 0]
After 3^{rd} second [1 1 1 0 0]
Total time taken = 3 seconds
Author:  admin2 
Tester:  mgch 
Tags  admin2 
Date Added:  1022017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 