오르내리기

길이가 $N$인 정수 수열이 주어진다. 엄격하게 증가한 뒤 엄격하게 감소하는 부분 수열 중 길이가 가장 긴 것을 구하라. 증가하는 부분의 마지막 위치와 감소하는 부분의 첫 위치는 같아야 한다. 부분 수열은 원래 수열에서 일부 원소를 제거하거나 아무것도 제거하지 않고 얻으며, 남은 원소의 순서는 바뀌지 않는다.

이 문제에서 엄격하게 증가하는 부분과 엄격하게 감소하는 부분의 길이는 각각 2 이상이어야 한다. 빈 부분 수열이나 길이가 1인 부분 수열은 증가도 감소도 하지 않는다. 아래 예시를 참고하라.

• 7은 증가도 감소도 하지 않는다.
• 1 1 1은 증가도 감소도 하지 않는다.
• 1 1 2는 증가도 감소도 하지 않는다.
• 1 2 7은 엄격하게 증가한다. 감소하지는 않는다.
• 3 2 1은 엄격하게 감소한다. 증가하지는 않는다.
• 8 9 3은 엄격하게 증가한 뒤 엄격하게 감소한다. 풀이가 찾아야 하는 것이 바로 이런 형태의 부분 수열이다.

첫 줄에 테스트 케이스의 개수를 나타내는 양의 정수 $T$ ($1 \le T \le 5 \cdot 10^4$)가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 리스트에 담긴 정수의 개수 $N$ ($3 \le N \le 2 \cdot 10^5$)이 주어진다. 둘째 줄에는 $N$개의 정수 $a_i$가 주어지며, 각 값은 부호 있는 32비트 정수 범위 ($-2^{31} \le a_i \le 2^{31}-1$)에 속한다.

모든 테스트 케이스에 등장하는 정수의 총개수는 $5 \cdot 10^5$을 넘지 않는다.

각 테스트 케이스마다 엄격하게 증가한 뒤 엄격하게 감소하는 부분 수열의 길이 중 최댓값을 음이 아닌 정수 하나로 출력한다. 예를 들어 예시 3에서 부분 수열 1 2 4 5 2 1이 가장 긴 오르내리기 부분 수열이므로 답은 $6$이다.