Grouping Increases (Codeforces 1919C)
Tags: Greedy, data structures

You are given an array $$$a$$$ of size $$$n$$$. You will do the following process to calculate your penalty:   Split array $$$a$$$ into two (possibly empty) subsequences$$$^\dagger$$$ $$$s$$$ and $$$t$$$ such that every element of $$$a$$$ is either in $$$s$$$ or $$$t^\ddagger$$$.  For an array $$$b$$$ of size $$$m$$$, define the penalty $$$p(b)$$$ of an array $$$b$$$ as the number of indices $$$i$$$ between $$$1$$$ and $$$m - 1$$$ where $$$b_i < b_{i + 1}$$$.  The total penalty you will receive is $$$p(s) + p(t)$$$. If you perform the above process optimally, find the minimum possible penalty you will receive.$$$^\dagger$$$ A sequence $$$x$$$ is a subsequence of a sequence $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by the deletion of several (possibly, zero or all) elements.$$$^\ddagger$$$ Some valid ways to split array $$$a=[3,1,4,1,5]$$$ into $$$(s,t)$$$ are $$$([3,4,1,5],[1])$$$, $$$([1,1],[3,4,5])$$$ and $$$([\,],[3,1,4,1,5])$$$ while some invalid ways to split $$$a$$$ are $$$([3,4,5],[1])$$$, $$$([3,1,4,1],[1,5])$$$ and $$$([1,3,4],[5,1])$$$.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the size of the array $$$a$$$.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output: For each test case, output a single integer representing the minimum possible penalty you will receive.

Note: In the first test case, a possible way to split $$$a$$$ is $$$s=[2,4,5]$$$ and $$$t=[1,3]$$$. The penalty is $$$p(s)+p(t)=2 + 1 =3$$$.In the second test case, a possible way to split $$$a$$$ is $$$s=[8,3,1]$$$ and $$$t=[2,1,7,4,3]$$$. The penalty is $$$p(s)+p(t)=0 + 1 =1$$$.In the third test case, a possible way to split $$$a$$$ is $$$s=[\,]$$$ and $$$t=[3,3,3,3,3]$$$. The penalty is $$$p(s)+p(t)=0 + 0 =0$$$.

Sample Inputs:
5
5
1 2 3 4 5
8
8 2 3 1 1 7 4 3
5
3 3 3 3 3
1
1
2
2 1

Sample Outputs:
3
1
0
0
0

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    ls = list(map(int, input().split()))
    l = 10000000000.0
    r = 10000000000.0
    cnt = 0
    for i in range(n):
        x = ls[i]
        if x <= l:
            l = x
        elif x > r:
            l = r
            r = x
            cnt += 1
        else:
            r = x
    print(cnt)
for _ in range(int(input())):
    solve()

Solution (Python):
from sys import stdin
import math
INF = float('inf')
input = stdin.readline

def read_str():
    return input().rstrip()

def read_int():
    return int(input().rstrip())

def read_lst():
    return list(map(int, input().rstrip().split()))

def read_map():
    return map(int, input().rstrip().split())

def ok(b):
    print('YES' if b else 'NO')

def solve():
    n = read_int()
    a = read_lst()
    l1 = l2 = INF
    p = 0
    for i in a:
        if l1 > l2:
            (l1, l2) = (l2, l1)
        if i <= l1:
            l1 = i
        elif i <= l2:
            l2 = i
        else:
            l1 = i
            p += 1
    print(p)

def main():
    for _ in range(read_int()):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
for _ in range(int(input())):
    N = int(input())
    (*A,) = map(int, input().split())
    x = y = N + 1
    ans = 0
    for a in A:
        if a <= x:
            x = a
        elif a <= y:
            y = a
        else:
            x = y
            y = a
            ans += 1
    print(ans)