Binary Inversions solution codeforces

Binary Inversions solution codeforces

You are given a binary array of length nn. You are allowed to perform one operation on it at most once. In an operation, you can choose any element and flip it: turn a 00 into a 11 or vice-versa.

What is the maximum number of inversions the array can have after performing at most one operation?

 A binary array is an array that contains only zeroes and ones.

 The number of inversions in an array is the number of pairs of indices i,ji,j such that i<ji<j and ai>ajai>aj.

Binary Inversions solution codeforces

The input consists of multiple test cases. The first line contains an integer tt (1t1041≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer nn (1n21051≤n≤2⋅105) — the length of the array.

The following line contains nn space-separated positive integers a1a1a2a2,…, anan (0ai10≤ai≤1) — the elements of the array.

It is guaranteed that the sum of nn over all test cases does not exceed 21052⋅105.

Binary Inversions solution codeforces

For each test case, output a single integer  — the maximum number of inversions the array can have after performing at most one operation.

Example
input

Copy
5
4
1 0 1 0
6
0 1 0 0 1 0
2
0 0
8
1 0 1 1 0 0 0 1
3
1 1 1
output

Copy
3
7
1
13
2

Binary Inversions solution codeforces

For the first test case, the inversions are initially formed by the pairs of indices (1,21,2), (1,41,4), (3,43,4), being a total of 33, which already is the maximum possible.

For the second test case, the inversions are initially formed by the pairs of indices (2,32,3), (2,42,4), (2,62,6), (5,65,6), being a total of four. But, by flipping the first element, the array becomes 1,1,0,0,1,01,1,0,0,1,0, which has the inversions formed by the pairs of indices (1,31,3), (1,41,4), (1,61,6), (2,32,3), (2,42,4), (2,62,6), (5,65,6) which total to 77 inversions which is the maximum possible.

 

Post navigation

Leave a Reply

Your email address will not be published.