PIIMA

Xotira 256 MB Vaqt 1000 ms

14

K-th subarray sum

Uzunligi $N$ bo‘lgan musbat sonlardan iborat $A$ massiv mavjud. Komiljon oldin bu massivning har bir qism massivi uchun uning elementlarini yig‘indisini yozib chiqdi. So‘ng yozilgan barcha sonlarni kamaymaslik tartibida saraladi va bu sonlar orasida qiymati $K$ -bo‘lganini tanlab oldi. Oradan biroz vaqt o‘tib Komiljon ushbu sonni unitib qo‘ydi. Endi u sizdan bu sonni topib berishni so‘radi. Unga yordam bering.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son - $N$ va $K$ . $(1 \le N \le 2 \cdot 10^5); (1 \le K \le \frac{N(N+1)}{2})$
Ikkinchi qatorda probel bilan ajratilgan $N$ ta son - $A$ massiv elementlari kiritiladi. $(0 \le A_i \le 10^9)$

Chiquvchi ma'lumotlar:

Ekranga yagona son, barcha qism massiv yig‘indilari orasida $K$ -kichigini chiqaring.

Misollar

#	input.txt	output.txt
1	2 1 1 2	1
2	6 7 4 12 5 0 3 9	8

Izoh:

1-testda $[1, 2]$ massivning 3 ta qism massivi mavjud, bular: $[1]$ ; $[2]$ ; $[1, 2]$ . Ularning yig‘indisi 1, 2, 3ga teng. $K=1$ holatda javob 1.

Masala E

K-th subarray sum