You have \(N\) fruits on a table with their weights written alongside them, these weights will be represented by an array \(W \) of length \(N\).

In a game called "Fruit Smash", you can use a stick to smash fruits. You have to smash in the order of left to right and you can start smashing from any fruit. The stick you will use downgrades in strength and will work only if the weight of the current fruit you are smashing is strictly less than the previously smashed fruit.

You can skip fruits in between as well. The number of fruits you smash is also your score.

Task
Your task is to find what is the maximum number of fruits you can smash in one go.

Example

Assumption:

\(​N = 5\)

\(W = [2, 10, 5, 6, 1]\)

Approach:

We can start smashing from \(2\). The next fruit that has lesser weight than \(2\) is \(1 \) which is in the \(5^{th}\) position, which results in \(2\) fruits smashing.

But we can achieve a better score if we start from the \(2^{nd}\) position and smash the fruit with weight \(10 \), then \(5 \), and then finally the fruit with weight \(1\) which makes our score as \(3 \), which is the maximum we can achieve.

Hence the answer is \(3\).

Function description

Complete the function solve provided in the editor. This function takes the following two parameters and returns the required answer:
\(N\): the number of fruits.
\(W\): the array representing the weights of the fruits in order.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

The first line contains \(T\) denoting the number of test cases. \(T\) also specifies the number of times you have to run the solve function on a different set of inputs.
For each test case:

The first line contains the integer \(N\).

The second line contains the integer array \(W\).

Output format
For each test case, print the answer in a new line.

Constraints

\(1 \leq T \leq 10\)
\(1 \leq N \leq 2000 \)

\(1 \leq W[i] \leq 10^{6}\)

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.