[Solution] LIS or Reverse LIS? Codeforces Solution | Codeforces Problem Solution 2022

[Solution] LIS or Reverse LIS? Codeforces Solution | Codeforces Problem Solution 2022

C. LIS or Reverse LIS?

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array 𝑎$a$ of 𝑛$n$ positive integers.

Let LIS(𝑎)$\text{LIS}(a)$ denote the length of longest strictly increasing subsequence of 𝑎$a$. For example,

• LIS([2,1⎯⎯,1,3⎯⎯])$\text{LIS}([2,\underset{\_}{1},1,\underset{\_}{3}])$ = 2$2$.
• LIS([3⎯⎯,5⎯⎯,10⎯⎯⎯⎯,20⎯⎯⎯⎯])$\text{LIS}([\underset{\_}{3},\underset{\_}{5},\underset{\_}{10},\underset{\_}{20}])$ = 4$4$.
• LIS([3,1⎯⎯,2⎯⎯,4⎯⎯])$\text{LIS}([3,\underset{\_}{1},\underset{\_}{2},\underset{\_}{4}])$ = 3$3$.

We define array 𝑎′$a^{\prime }$ as the array obtained after reversing the array 𝑎$a$ i.e. 𝑎′=[𝑎𝑛,𝑎𝑛−1,…,𝑎1]$a^{\prime }=[a_n,a_{n-1},\dots ,a_1]$.

The beauty of array 𝑎$a$ is defined as 𝑚𝑖𝑛(LIS(𝑎),LIS(𝑎′))$min(\text{LIS}(a),\text{LIS}(a^{\prime }))$.

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 the test cases follows.

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

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,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤109)$(1\le a_i\le {10}^9)$  — the elements of the array 𝑎$a$.

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

Output

For each test case, output a single integer  — the maximum possible beauty of 𝑎$a$ after rearranging its elements arbitrarily.