Longest Increasing Subsequence

You are given an array of integers representing prices. Your task is to compute the length of the Longest Increasing Subsequence (LIS) in the array. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Formally, for an array \(A = [a_1, a_2, \ldots, a_N]\), you need to find the maximum integer \(k\) such that there exist indices \(1 \le i_1 < i_2 < \cdots < i_k \le N\) with \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\). The answer is the length of such a subsequence, which can be denoted as \(\text{LIS}\).

This problem can be efficiently solved using dynamic programming combined with binary search, achieving a time complexity of \(O(N \log N)\).

inputFormat

The input is read from standard input and has the following format:

• The first line contains an integer \(T\), the number of test cases.
• Each test case consists of two lines:
  • The first line contains an integer \(N\), the number of elements in the array.
  • The second line contains \(N\) space-separated integers representing the array elements.

outputFormat

For each test case, output a single line containing the length of the longest increasing subsequence.

The outputs for consecutive test cases should appear in the same order as the input test cases.

## sample

2
7
10 20 10 30 20 50 60
5
5 3 4 8 6

5
3

</p>