• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

تصویر زیر، نمای کوه کدکاپ است. می‌دانیم ارتفاع این کوه از هر دو طرف تا قله همواره صعودی است. توجه کنید ممکن است در بازه‌ای ارتفاع ثابت بماند اما هیچوقت در مسیر قله، ارتفاع کاهش نمی‌یابد.

زمین‌شناسان $n$ نقطه در کوه کدکاپ را انتخاب کرده و ارتفاع کوه را در آن نقاط را اندازه گیری کرده‌اند. ارتفاع این نقاط را به ترتیب از چپ به راست با $h_1, h_2, \dots, h_n,$ مشخص می‌کنیم. با این حال اندازه‌گیری زمین‌شناسان خطا دارد و ارتفاع واقعی کوه در این $n$ نقطه برابر با اعداد اندازه‌گیری شده نیست. ارتفاع واقعی کوه را در این $n$ نقطه با $H_1, H_2, \dots, H_n,$ نشان می‌دهیم.

بنابراین با توجه به ویژگی کوه کدکاپ می‌دانیم دنباله‌ی $H$ در ابتدا صعودی و سپس نزولی است. یعنی عدد صحیحی مثل $i$ که $1 \leq i \leq n$ وجود دارد به طوری که $H_1, H_2, \dots, H_i,$ تشکیل یک دنباله‌ی صعودی و دنباله‌ی $H_{i+1}, H_{i+2}, \dots, H_n,$ تشکیل یک دنباله‌ی نزولی بدهد.

به یک دنباله مثل $a_1, a_2, \dots, a_n,$ صعودی می‌گوییم هرگاه $a_1 \leq a_2 \leq \dots \leq a_n,$ باشد. به یک دنباله مثل $a_1, a_2, \dots, a_n,$ نزولی می‌گوییم هرگاه $a_1 \geq a_2 \geq \dots \geq a_n,$ باشد.

می‌گوییم خطای اندازه‌گیری $k$ است اگر هر کدام از $h_i$ها حداکثر $k$ واحد با $H_i$ اختلاف داشته باشد. ($|h_i-H_i|\leq k,$)

به شما دنباله‌ی $h_1, h_2, \dots, h_n,$ داده می‌شود. از شما می‌خواهیم کمینه خطای ممکن برای این داده‌ها را حساب کنید. یعنی کوچک‌ترین $k$ی صحیحی را پیدا کنید که دنباله‌ای مثل $H$ وجود داشته باشد که هر عضوش با $h$ حداکثر $k$ واحد اختلاف داشته باشد و در ابتدا صعود و سپس نزولی باشد.

ورودی

در سطر اول ورودی، عدد صحیح $t$ آمده که تعداد تست‌ها را نشان می‌دهد. $$1 \leq t \leq 200,000$$

در سطر اول هر تست، عدد صحیح و مثبت $n$ آمده که تعداد اعداد آرایه را نشان می‌دهد. $$1 \leq n \leq 200,000$$

در سطر دوم هر تست، $n$ عدد $h_1, h_2, \dots, h_n,$ با فاصله از هم آمده است. $$1 \leq h_i \leq 10^9$$ توجه کنید که با وجود این که $h_i$ عددی است، $H_i$ ممکن است هر عددی شامل اعداد منفی یا بزرگ‌تر از $10^9$ باشد.

تضمین می‌شود مجموع $n$ها برای همه‌ی تست‌ها حداکثر ۲۰۰،۰۰۰ باشد.

خروجی

در $t$ سطر کمینه خطای ممکن برای هر تست را به ترتیب چاپ کنید.

مثال

ورودی نمونه ۱

2
5
10 20 30 20 10
7
1 4 1 3 2 1 3

خروجی نمونه ۱

0
1