[Solution] AND Sorting Codeforces Solution | Codeforces Problem Solution 2022

[Solution] AND Sorting Codeforces Solution | Codeforces Problem Solution 2022

B. AND Sorting

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a permutation 𝑝$p$ of integers from 0$0$ to 𝑛−1$n-1$ (each of them occurs exactly once). Initially, the permutation is not sorted (that is, 𝑝𝑖>𝑝𝑖+1$p_i>p_{i+1}$ for at least one 1≤𝑖≤𝑛−1$1\le i\le n-1$).

The permutation is called 𝑋$X$-sortable for some non-negative integer 𝑋$X$ if it is possible to sort the permutation by performing the operation below some finite number of times:

• Choose two indices 𝑖$i$ and 𝑗$j$ (1≤𝑖<𝑗≤𝑛)$(1\le i<j\le n)$ such that 𝑝𝑖&𝑝𝑗=𝑋$p_i\mathrm{\&}{p}_j=X$.
• Swap 𝑝𝑖$p_i$ and 𝑝𝑗$p_j$.

Here &$\mathrm{\&}$ denotes the bitwise AND operation.

Solution Click Below:-  CLICK HERE

Input

The input consists of multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤104)$(1\le t\le {10}^4)$  — the number of test cases. Description of test cases follows.

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

Palindromic Indices Codeforces Solution

AND Sorting Codeforces Solution 

LIS or Reverse LIS? Codeforces Solution

Circular Spanning Tree Codeforces Solution

Unordered Swaps Codeforces Solution

MCMF? Codeforces Solution

The second line of each test case contains 𝑛$n$ integers 𝑝1,𝑝2,...,𝑝𝑛$p_1,p_2,...,p_n$ (0≤𝑝𝑖≤𝑛−1$0\le p_i\le n-1$, all 𝑝𝑖$p_i$ are distinct)  — the elements of 𝑝$p$. It is guaranteed that 𝑝$p$ is not sorted.

It is guaranteed that the sum of 𝑛$n$ over all cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case output a single integer — the maximum value of 𝑋$X$ such that 𝑝$p$ is 𝑋$X$-sortable.