406826: GYM102566 C Emojis

Georgel wants to make a girlfriend, so he decided to impress the girl he is currently talking to through text messages. Now, it is currently 2020, and everybody knows that you are cool only if you text solely with emojis in a non-decreasing order. Georgel is quite the antisocial guy, so he naturally does not know of this convention – in fact, he is beyond salvation. He does use emojis, but in a blasphemous manner.

You, contestant, are a lovely, caring person and decided to help him out of your own free will by removing some of the emojis of some text messages that he has yet to send.

You are given $$$T$$$ ($$$1 \leq T \leq 100.000)$$$ text messages of $$$N$$$ emojis $$$N$$$ ($$$1 \leq N \leq 100.000$$$) which can be understood as integers ranging from $$$1$$$ to $$$10^9$$$. To save Georgel, we ask of you that you remove some of them in order to obtain the largest non-decreasing substring possible. However, since the longer the text, the better the message, you must minimise the number of emojis removed.

Bear in mind that you only ought to remove the emojis which interfere with said substring. For instance, if the longest non-decreasing substring that can be obtained has elements ranging from index $$$i$$$ to index $$$j$$$, the emojis whose positions belong to $$$[1, i-1]$$$ and $$$[j+1, N]$$$ need not be removed.

It is guaranteed that the the sum of $$$N$$$'s over test cases will not exceed $$$10^6$$$.

The first line of input will contain a single positive integer, $$$T$$$, representing the number of test cases. Each test case will consist of two lines.

The first line will contain a single positive integer, $$$N$$$, representing the number of emojis in the text message.

The second line will contain $$$N$$$ positive integers $$$a_i \ (1 \leq i \leq N)$$$, each of them representing an emoji.

The output should contain, on a single line per test case, two integers $$$X$$$, $$$Y$$$, representing the length of the longest increasing substring of emojis that can be obtained and the number of emojis that has been removed.

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

4 3

The longest increasing substring of emojis that can be obtained is $$$1$$$ $$$3$$$ $$$3$$$ $$$3$$$. In order to obtain this substring, emojis $$$5$$$, $$$6$$$ and $$$1$$$ must be removed.