У Алисы есть упорядоченный по неубыванию массив целых чисел $$$a_1, a_2, \ldots, a_n$$$. Другими словами, изначально для всех $$$1 \leq i < n$$$ верно, что $$$a_i \leq a_{i + 1}$$$.
Алиса ровно один раз выбрала некоторый подотрезок этого массива (возможно, пустой) и перемешала элементы в нём. Например, если $$$a = [1, 2, 3, 4, 5]$$$, то Алиса могла выбрать подотрезок элементов $$$[a_2, a_3, a_4]$$$ и как угодно перемешать эти элементы между собой местами. Тогда у неё может получиться любой из шести следующих массивов: $$$[1, 2, 3, 4, 5], [1, 2, 4, 3, 5], [1, 3, 2, 4, 5], [1, 3, 4, 2, 5], [1, 4, 2, 3, 5], [1, 4, 3, 2, 5]$$$. Если Алиса выбирает пустой подотрезок, то массив не изменяется.
Боб не видел изначального массива и хочет понять, каким мог быть наибольший и наименьший размер выбранного Алисой подотрезка. Помогите ему решить эту задачу.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.
В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество элементов в массиве.
Во второй строке каждого набора содержится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива Алисы после того, как она перемешала какой-то его подотрезок.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите через пробел два целых числа —– наименьший и наибольший размер подотрезка, выбранного Алисой.
455 3 4 2 131 2 31161 3 2 2 1 3
5 50 30 14 6
В первом наборе входных данных минимальное число стоит последним, а максимальное — первым, поэтому размеры наименьшего и наибольшего подотрезков совпадают и равны $$$5$$$.
Во втором наборе входных данных все числа стоят на своём месте, поэтому наименьший возможный подотрезок имеет размер $$$0$$$, наибольший же размер $$$3$$$.