Longest Non-Decreasing Subsequence

Given an array of integers, your task is to find the length of the longest non-decreasing subsequence in the array.

A non-decreasing subsequence is defined as a sequence of indices \(i_1, i_2, \dots, i_k\) such that \(a[i_1] \leq a[i_2] \leq \cdots \leq a[i_k]\). The solution is required to run in \(O(n \log n)\) time using binary search techniques.

For example, given the array [10, 9, 2, 5, 3], one possible longest non-decreasing subsequence is [2, 5] (among other possibilities), so the answer is 2.

You will be given multiple test cases. For each test case, the first number is the size of the array followed by the array elements.

Hint: To handle equal elements correctly, use the update rule using \(\text{upper_bound}\), i.e. find the first element greater than the current value and update that position.

inputFormat

The first line contains an integer (T), the number of test cases. Each test case starts with an integer (N) representing the size of the array, followed by (N) space-separated integers.

outputFormat

For each test case, output a single integer representing the length of the longest non-decreasing subsequence. Each result should be printed on a separate line.## sample

2
5 10 9 2 5 3
6 1 3 2 3 4 5

2
5