Maximum Crossings (Hard Version) Codeforces Solution | Codeforces Problem Solution 2022

Maximum Crossings (Hard Version) Codeforces Solution | Codeforces Problem Solution 2022

H2. Maximum Crossings (Hard Version)

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

The only difference between the two versions is that in this version 𝑛≤2⋅105$n\le 2\cdot {10}^5$ and the sum of 𝑛$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

A terminal is a row of 𝑛$n$ equal segments numbered 1$1$ to 𝑛$n$ in order. There are two terminals, one above the other.

Solution Click Below:-  CLICK HERE

You are given an array 𝑎$a$ of length 𝑛$n$. For all 𝑖=1,2,…,𝑛$i=1,2,\dots ,n$, there should be a straight wire from some point on segment 𝑖$i$ of the top terminal to some point on segment 𝑎𝑖$a_i$ of the bottom terminal. For example, the following pictures show two possible wirings if 𝑛=7$n=7$ and 𝑎=[4,1,4,6,7,7,5]$a=[4,1,4,6,7,7,5]$.

A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red.

What is the maximum number of crossings there can be if you place the wires optimally?

Input

The first line contains an integer 𝑡$t$ (1≤𝑡≤1000$1\le t\le 1000$) — the number of test cases.

The first line of each test case contains an integer 𝑛$n$ (1≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$) — the length of the array.

Lucky? Codeforces Solution

Equal Candies Codeforces Solution

Most Similar Words Codeforces Solution

X-Sum Codeforces Solution

Eating Queries Codeforces Solution

Longest Strike Codeforces Solution

White-Black Balanced Subtrees Codeforces Solution

Maximum Crossings (Easy Version) Codeforces Solution

Maximum Crossings (Hard Version) Codeforces Solution

The second line of each test case contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤𝑛$1\le a_i\le n$) — the elements of the array.

The sum of 𝑛$n$ across all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.

Join Now for Solution:-