Данная задача состоит из нескольких наборов входных данных.

В первой строке каждого набора задано единственное число $t$ ($1 \leq t \leq 5 \cdot 10^4$) --- количество  наборов входных данных. Затем идет их описание.

В первой строке каждого набора задано число $n$ ($3 \leq n \leq 2 \cdot 10^5$) --- размер перестановки.

Во второй строке задана перестановка $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$).

Гарантируется, что сумма $n$ по всем тестовым случаям не превосходит $2 \cdot 10^5$