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

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

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

توضیح تصویر

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

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

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

به شما دنباله‌ی h1,h2,,hn,h_1, h_2, \dots, h_n, داده می‌شود. از شما می‌خواهیم کمینه خطای ممکن برای این داده‌ها را حساب کنید. یعنی کوچک‌ترین kkی صحیحی را پیدا کنید که دنباله‌ای مثل HH وجود داشته باشد که هر عضوش با hh حداکثر kk واحد اختلاف داشته باشد و در ابتدا صعود و سپس نزولی باشد.

ورودی

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

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

در سطر دوم هر تست، nn عدد h1,h2,,hn,h_1, h_2, \dots, h_n, با فاصله از هم آمده است. 1hi1091 \leq h_i \leq 10^9 توجه کنید که با وجود این که hih_i عددی است، HiH_i ممکن است هر عددی شامل اعداد منفی یا بزرگ‌تر از 10910^9 باشد.

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

خروجی

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

مثال

ورودی نمونه ۱

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

خروجی نمونه ۱

0
1
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.