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

به $n$ آجر که در یک ردیف کنار هم قرار گرفته‌اند یک «لایه آجر» می‌گوییم. آجر‌ها را به ترتیب با اعداد $1$ تا $n$ شماره‌گذاری کنید. آجر $i$ام یک عدد مثل $a_i$ دارد که «استحکام» آن را نشان می‌دهد.

به یک لایه آجر «مستحکم» می‌گوییم اگر دنباله‌ی $a_1, a_2, \dots, a_n$ یک دنباله غیرنزولی باشد یعنی $a_1 \leq a_2 \leq \dots \leq a_n,$ باشد.

برای «مستحکم» کردن یک دیوار، در هر حرکت می‌توانیم یک بازه‌ از آجرها را انتخاب و سپس به «استحکام» تمام آن‌ها $x$ واحد اضافه کند. ($x$ در تمام مراحل ثابت است و به شما داده می‌شود.) یعنی می‌توان دو عدد $l$ و $r$ که $1 \leq l \leq r \leq n$ است را انتخاب کرد و وضعیت دنباله را به

$$a_1, a_2, \dots, a_{l - 1}, a_l + x, a_{l + 1} + x, \dots, a_{r - 1} + x, a_r + x, a_{r + 1}, \dots, a_n$$

تغییر داد.

کمترین تعداد حرکتی که نیاز داریم تا این «لایه آجر» مستحکم شود، را خروجی دهید یا بگویید مستحکم کردن این دیوار غیرممکن است.

برای ساختن یک ساختمان $q$ لایه آجر باید مستحکم شود. دنباله‌ی اولیه استحکام آجرها و مقدار $x$ برای هر لایه به شما داده می‌شود و از شما می‌خواهیم مسئله را برای هر لایه به صورت جداگانه حل کنید.

برای بهتر متوجه شدن سوال، نمونه‌ها را مشاهده کنید.

ورودی

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

در $2q$ سطر بعدی ورودی، به ترتیب به ازای هر لایه در ابتدا در یک سطر $n$ و $x$ نشان‌دهنده تعداد آجرهای آن لایه و مقدار استحکامی که در هر حرکت می‌تواند اضافه کند آمده است.

$$1 \leq n \leq 100 , 000$$ $$-100 , 000 \leq x \leq 100 , 000$$

سپس در سطر بعدی به ترتیب $n$ عدد، $a_1, a_2, \dots, a_n,$ نشان دهنده استحکام اولیه‌ی آجرهای آن لایه آمده است. تعداد کل آجرها حداکثر $100,000$ است.

$$-100 ,000 \leq a_i \leq 100 , 000$$

خروجی

خروجی شما باید شامل $q$ سطر باشد. در هر سطر کمترین تعداد حرکتی را خروجی دهید که بتوان بعد از این تعداد حرکت استحکام آجرهای این لایه را غیرنزولی کرد. اگر انجام این کار ممکن نیست -1 چاپ کنید.

مثال

ورودی نمونه ۱

4
2 2
-3 3
4 1
-2 -4 4 -3
3 0
-73 -4 -5
1 3
1

خروجی نمونه ۱

0
9
-1
0

در مثال اول، آرایه‌ی $[-3, 3]$ صعودی است و نیاز به هیچ عملیاتی ندارد. پس پاسخ مسئله برابر ۰ است.

در مثال دوم، آرایه‌ی اولیه $[-2, -4, 4, -3]$ است و هر بار می‌توانیم یک بازه را انتخاب کرده و $x = 1$ واحد به آن اضافه کنیم. اگر دنباله‌ی حرکت‌ها به صورت زیر باشد، بعد از ۹ حرکت به یک آرایه صعودی می‌رسیم.

1. $[-2, -4, 4, -3] \to$
2. $[-2, -3, 5, -2] \to$
3. $[-2, -2, 6, -1] \to$
4. $[-2, -2, 6, 0] \to$
5. $[-2, -2, 6, 1] \to$
6. $[-2, -2, 6, 2] \to$
7. $[-2, -2, 6, 3] \to$
8. $[-2, -2, 6, 4] \to$
9. $[-2, -2, 6, 5] \to [-2, -2, 6, 6]$

در مثال سوم مقدار $x = 0$ است، پس انجام عملیات، باعث تغییری در وضعیت آرایه نمی‌شود و هیچ‌وقت نمی‌توانیم آن را غیرنزولی کنیم.

در مثال چهارم آرایه اولیه تک عضوی است. پس غیرنزولی نیز هست.