Фермер Джон выстроил коров в ряд и хочет их сфотографировать.
Каждая из \(N\) коров \((1 \le N \le 10^5)\) имеет целую высоту от \(1\) до \(N\).
ФД хочет сфотографировать их в определённом порядке.
Если коровы с высотами \(h_1, \dots, h_K\) стоят в ряд слева направо,
он хочет, чтобы для их высот выполнялись следующие три свойства:
- Чтобы высоты коров сначала возрастали, а потом убывали.
Формально, должно существовать такое целое число \(i\), что
\(h_1 \le \dots \le h_i \ge \dots \ge h_K\).
- Чтобы рядом стояли коровы с одинаковой высотой.
Формально, \(h_i \neq h_{i+1}\) для \(1 \le i < K\).
- Чтобы фотография была симметричной.
Формально, если \(i + j = K+1\), then \(h_i = h_j\).
ФД хочет, чтобы на фотографии было как можно больше коров.
А именно, ФД может удалить некоторых коров и переупорядочить оставшихся коров.
Вычислите максимальное количество коров, которые ФД может выставить
на своей фотографии, удовлетворив указанные свойства.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Имеется множество подтестов.
Первая строка ввода содержит одно целое число \(T\) (\(1 \leq T \leq 10^5\)),
обозначающее количество подтестов. Далее следуют \(T\) подтестов.
Первая строка каждого подтеста содержит одно целое число \(N\). Вторая строка
каждого подтеста содержит \(N\) целых чисел, высоты имеющихся \(N\) коров.
Эти числа в интервале от \(1\) до \(N\).
Гарантируется, что сумма \(N\) по всем подтестам не превысит \(10^6\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(T\) строк, \(i\)-ая строка содержит ответ на \(i\)-ый подтест -
целое число, обозначающее максимальное количество коров, которых ФД
может включить в фотографию.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
1 1 2 3
4
3 3 2 1
|
3
1
|