Бесси экспериментирует с мощным имплантатом копыта, который способен создавать
мощные ударные волны. Перед ней выстроено \(N\) (\(2 \leq N \leq 10^5\)) плиток,
для разрушения которых требуется мощность не менее \(p_0,p_1,\dots,p_{N-1}\),
соответственно (\(0 \leq p_i \leq 10^{18}\)).
Бесси может применить силу, ударив по определенной плитке,
но из-за странной природы ее имплантата, она не применит никакой силы к плитке,
которую она пробьет. Вместо этого, если она решит ударить плитку \(x\) один раз,
где \(x\) — это целое число в диапазоне \([0,N-1]\),
она применит \(|i-x|\) силу к плитке \(i\) для всех целых чисел \(i\) в диапазоне
\([0,N-1]\). Эта сила также является кумулятивной, поэтому применение \(2\) силы
дважды к плитке применит в общей сложности \(4\) силы к плитке.
Определите наименьшее количество ударов, необходимое для разбивания всех плиток.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(T\) (
\(1 \leq T \leq 100\)) представляющее количество подтестов.
Строка \(2t\) содержит одно целое число \(N\), количество плиток в подтесте \(t\).
Строка \(2t+1\) содержит \(N\) разделённых одиночными пробелами чисел
\(p_0,p_1, \ldots, p_{N-1}\) представляющих что плитку \(i\) разрушит удар силы \(p_i\).
Гарантируется, что сумма всех \(N\) в одном тесте не превысит \(5\cdot 10^5\).
ФОРМАТ ВЫВОДА (на экран / stdout):
\(T\) строк, \(i\)-ая строка представляет ответна \(i\)-ый подтест.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5
0 2 4 5 8
5
6 5 4 5 6
5
1 1 1 1 1
5
12 10 8 6 4
7
6 1 2 3 5 8 13
2
1000000000000000000 1000000000000000000
|
2
3
2
4
4
2000000000000000000
|