[Solution] Odd Subarrays Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Odd Subarrays Codeforces Solution | Codeforces Problem Solution 2022

B. Odd Subarrays

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

For an array [b1,b2,…,bm]$[b_1,b_2,\dots ,b_m]$ define its number of inversions as the number of pairs (i,j)$(i,j)$ of integers such that 1≤i<j≤m$1\le i<j\le m$ and bi>bj$b_i>b_j$. Let's call array b$b$ odd if its number of inversions is odd.

For example, array [4,2,7]$[4,2,7]$ is odd, as its number of inversions is 1$1$, while array [2,1,4,3]$[2,1,4,3]$ isn't, as its number of inversions is 2$2$.

You are given a permutation [p1,p2,…,pn]$[p_1,p_2,\dots ,p_n]$ of integers from 1$1$ to n$n$ (each of them appears exactly 

Solution Click Below:-  CLICK HERE

once in the permutation). You want to split it into several consecutive subarrays (maybe just one), so that the number of the odd subarrays among them is as large as possible.

What largest number of these subarrays may be odd?

Input

The first line of the input contains a single integer t$t$ (1≤t≤105$1\le t\le {10}^5$)  — the number of test cases. The description of the test cases follows.

Everything Everywhere All But One Codeforces Solution

Odd Subarrays Codeforces Solution

Circular Local MiniMax Codeforces Solution

Linguistics Codeforces Solution

Bring Balance Codeforces Solution 

Permutation Weight (Easy Version) Codeforces Solution

The first line of each test case contains a single integer n$n$ (1≤n≤105$1\le n\le {10}^5$)  — the size of the permutation.

The second line of each test case contains n$n$ integers p1,p2,…,pn$p_1,p_2,\dots ,p_n$ (1≤pi≤n$1\le p_i\le n$, all pi$p_i$ are distinct)  — the elements of the permutation.

The sum of n$n$ over all test cases doesn't exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case output a single integer  — the largest possible number of odd subarrays that you can get after splitting the permutation into several consecutive subarrays.