LaIS
Let's call a sequence $$$b_1, b_2, b_3 \dots, b_{k - 1}, b_k$$$ almost increasing if $$$$$$\min(b_1, b_2) \le \min(b_2, b_3) \le \dots \le \min(b_{k - 1}, b_k).$$$$$$ In particular, any sequence with no more than two elements is almost increasing.You are given a sequence of integers $$$a_1, a_2, \dots, a_n$$$. Calculate the length of its longest almost increasing subsequence.You'll be given $$$t$$$ test cases. Solve each test case independently.Reminder: a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
In the first test case, one of the optimal answers is subsequence $$$1, 2, 7, 2, 2, 3$$$.In the second and third test cases, the whole sequence $$$a$$$ is already almost increasing.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of independent test cases.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — the length of the sequence $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the sequence itself.It's guaranteed that the total sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.
For each test case, print one integer — the length of the longest almost increasing subsequence.
import bisect as bs
for _ in range(int(input())):
    (n, a) = (int(input()), list(map(int, input().split())))
    (stack, m, p) = ([a[0]], [], [(1000000, 0)])
    for v in a[1:]:
        k = bs.bisect_right(m, v)
        if k == len(m):
            stack.append(v)
            m.append(min(stack[-1], stack[-2]))
        else:
            stack[k + 1] = m[k] = v
        while p[-1][0] <= v:
            (vv, kk) = p.pop()
            m[kk] = min(m[kk], vv)
        if k + 1 < len(m):
            p.append((v, k + 1))
    print(len(stack))
import bisect as bs
for _ in range(int(input())):
    (n, a) = (int(input()), list(map(int, input().split())))
    (stack, m, p) = ([a[0]], [], [(1000000, 0)])
    for v in a[1:]:
        k = bs.bisect_right(m, v)
        if k == len(m):
            stack.append(v)
            m.append(min(stack[-1], stack[-2]))
        else:
            stack[k + 1] = m[k] = v
        while p[-1][0] <= v:
            (vv, kk) = p.pop()
            m[kk] = min(m[kk], vv)
        if k + 1 < len(m):
            p.append((v, k + 1))
    print(len(stack))
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):

    def __init__(self, file):
        self.newlines = 0
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
    return map(int, sys.stdin.readline().split())

def RLL():
    return list(map(int, sys.stdin.readline().split()))

def N():
    return int(input())

def S():
    return input().strip()

def print_list(l):
    print(' '.join(map(str, l)))
import bisect as bs
for _ in range(N()):
    n = N()
    a = RLL()
    (stack, m, p) = ([a[0]], [], [(1000000, 0)])
    for v in a[1:]:
        k = bs.bisect_right(m, v)
        if k == len(m):
            stack.append(v)
            m.append(min(stack[-1], stack[-2]))
        else:
            stack[k + 1] = m[k] = v
        while p[-1][0] <= v:
            (vv, kk) = p.pop()
            m[kk] = min(m[kk], vv)
        if k + 1 < len(m):
            p.append((v, k + 1))
    print(len(stack))