Masala E

Asilbekda uzunligi $N$ga teng $A$ massiv hamda $T$ soni bor. Asilbek barcha $1 \le l \le r \le N$ bo‘lgan oraliqlar ichidan $F(l, r) \le T$ bo‘lgan oraliqlar sonini topmoqchi. Siz unga yordam bering.

$F(l, r)$ quyidagicha hisoblanadi:
- $B_1=A_l; B_2=A_{l+1}; ...; B_{r-l+1}=A_r$ massiv bo'lsin
- Bitta amalda $B$ning ixtiyoriy elementini 1ga oshirish, yoki 1ga kamaytirish mumkin.
- $B$ massiv barcha elementlarini teng qilish uchun kerak bo'ladigan minimal amallar soni $F(l, r)$ ga teng bo'ladi.

Masalan, $A=[4,2,8,5]$. Bunda $F(1, 2)=2$; $F(3,3)=0$ hamda $F(1, 4) = 7$.

Birinchi qatorda ikkita butun son - $N$ va $T$ sonlari kiritiladi. $1 \le N \le 5 \cdot 10^5$; $0 \le T \le 5 \cdot 10^{14}$

Ikkinchi qatorda $N$ta butun son, $A$ massiv elementlari kiritiladi. $0 \le A_i \le 10^9)$

Berilgan $A$ massiv uchun $F(l, r) \le T$ shartni bajaradigan $1 \le l \le r \le N$ juftliklar sonini chop eting.