Read problem statements in [Mandarin], [Bengali], [Russian], and [Vietnamese] as well.

Chef has a sequence A_{1}, A_{2}, \ldots, A_{N}. Let's call a contiguous subsequence of A a *segment*.

A segment is *good* if it can be divided into at most K segments such that the sum of elements in each of these sub-segments is at most S.

You need to find the maximum number of elements in a good segment.

------ Input Format ------ 

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains three space-separated integers N, K and S.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.

------ Output Format ------ 

For each test case, print a single line containing one integer — the maximum length of a good segment.

------ Constraints ------ 

$1 ≤T ≤150,000$
$1 ≤K ≤N ≤10^{5}$
$1 ≤S ≤10^{9}$
$1 ≤A_{i} ≤S$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^{6}$

------ subtasks ------ 

Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
2
5 2 5
1 3 2 1 5
5 3 5
5 1 5 1 1
----- Sample Output 1 ------ 
4
4
----- explanation 1 ------ 
Example case 1: One of the segments with length $4$ is $[1, 3, 2, 1]$. It can be divided into two segments $[1, 3]$ and $[2, 1]$ whose sums are at most $S = 5$.

Difficulty: VERY_HARD
Tags: Sorting

Tree queries

Range queries
Skill types: Sorting

Range queries

Starter code:

Solutions:
def build(N, start_index):
	up = [[None] * N for _ in range(20)]
	up[0] = start_index
	for i in range(1, 20):
		for j in range(N):
			p = up[i - 1][j]
			if p == -1:
				up[i][j] = -1
			else:
				up[i][j] = up[i - 1][p]
	return up

def call(up, node, K):
	(last, jump) = (node, 1)
	for i in range(19):
		if node == -1:
			break
		if K & jump:
			node = up[i][node]
		jump <<= 1
	return last - node

def solve(nums, N, K, S):
	(start_index, j, curr) = ([], 0, 0)
	for i in range(N):
		curr += nums[i]
		while curr > S:
			curr -= nums[j]
			j += 1
		start_index.append(j - 1)
	up = build(N, start_index)
	res = 0
	for i in range(N - 1, -1, -1):
		res = max(res, call(up, i, K))
	return res
T = int(input())
for _ in range(T):
	(N, K, S) = tuple(map(int, input().split()))
	nums = list(map(int, input().split()))
	print(solve(nums, N, K, S))


import math, sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	a = list(map(int, input().split()))
	d = {}
	(l, r, ac) = (0, 0, 0)
	while r < n:
		if ac + a[r] <= s:
			ac += a[r]
			r += 1
		else:
			d[l] = r
			ac -= a[l]
			l += 1
	d[l] = r
	last = l
	for i in range(last, n + 1):
		d[i] = n
	best = 0
	c = [d]
	for i in range(int(math.log(k, 2))):
		(d, nou_d) = (c[-1], {})
		for k2 in d:
			nou_d[k2] = d[d[k2]]
		c.append(nou_d)
	l = bin(k)[2:][::-1]
	for d in c[0]:
		st = d
		if n - st <= best:
			break
		for (i, v) in enumerate(l):
			if v == '1':
				d = c[i][d]
				if d == n:
					break
		best = max(best, d - st)
	print(best)


import math, os, io, sys
from collections import Counter
import heapq
from collections import deque
import bisect

def getList(method=int):
	return list(map(method, input().split()))

def getInt():
	return int(input())

def solve():
	(n, k, s) = getList()
	a = getList()
	pref = [0] * n
	pref[0] = a[0]
	for i in range(1, n):
		pref[i] = pref[i - 1] + a[i]
	nxt = [0] * n
	ans = [0] * n
	for i in range(n):
		bf = pref[i - 1] if i > 0 else 0
		nxt[i] = bisect.bisect_right(pref, bf + s)
		ans[i] = i
	nxt.append(n)
	b = bin(k)[2:][::-1]
	for (j, bit) in enumerate(b):
		if bit == '1':
			for i in range(n):
				ans[i] = nxt[ans[i]]
		for i in range(n):
			nxt[i] = nxt[nxt[i]]
	mx = 0
	for i in range(n):
		mx = max(mx, ans[i] - i)
	return mx
for _ in range(getInt()):
	print(solve())


from math import gcd
import bisect as bs
for i in range(int(input())):
	(n, k, s) = map(int, input().split())
	l = list(map(int, input().split()))
	pre = [0] * (n + 1)
	for i in range(1, n + 1):
		pre[i] = pre[i - 1] + l[i - 1]
	next = [0] * (n + 2)
	next[0] = 0
	for i in range(1, n + 1):
		next[i] = bs.bisect(pre, s + pre[i - 1], i, n + 1)
	next[n + 1] = n + 1
	ans = [i for i in range(n + 2)]
	for i in range(21):
		if 1 << i & k:
			for j in range(1, n + 2):
				ans[j] = next[ans[j]]
		for j in range(1, n + 2):
			next[j] = next[next[j]]
	mx = 0
	for i in range(1, n + 1):
		mx = max(mx, ans[i] - i)
	print(mx)


def solver():
	suf = list(range(N + 1))
	right = total = 0
	for i in range(N):
		while right < N and total + arr[right] <= S:
			total += arr[right]
			right += 1
		suf[i] = right
		if right > i:
			total -= arr[i]
		else:
			right += 1
	ans = list(range(N + 1))
	for i in range(20):
		if K >> i & 1:
			for j in range(N):
				ans[j] = suf[ans[j]]
		for k in range(N):
			suf[k] = suf[suf[k]]
	return max(map(lambda x: ans[x] - x, range(N)))
T = int(input())
for t in range(T):
	(N, K, S) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(solver())


from math import floor, gcd, sqrt, ceil
from collections import Counter, defaultdict, deque
from itertools import combinations
from heapq import heapify, heappop, heappush
from bisect import bisect_left, bisect_right
import sys
input = lambda : sys.stdin.readline()

def main():
	for _ in range(int(input())):
		(n, k, s) = list(map(int, input().split()))
		a = list(map(int, input().split()))
		x = [0]
		for i in a:
			x.append(x[-1] + i)
		ans = [0] * (n + 1)
		for i in range(0, n + 1):
			ans[i] = bisect_right(x, x[i] + s) - i - 1
		for i in range(n):
			ans[i] = i + ans[i]
		ans1 = [i for i in range(n)]
		ans[-1] = n
		for i in range(20):
			if k & 1 << i:
				for j in range(n):
					ans1[j] = ans[ans1[j]]
			for j in range(n):
				ans[j] = ans[ans[j]]
		print(max([j - i for (i, j) in enumerate(ans1)]))
main()


from collections import defaultdict
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	a = list(map(int, input().split()))
	(l, r, ac, d) = (0, 0, 0, {})
	while r < n:
		if ac + a[r] <= s:
			ac += a[r]
			r += 1
		else:
			d[l] = r
			ac -= a[l]
			l += 1
	for l in range(l, n):
		d[l] = n
	rev = defaultdict(list)
	for (k2, v) in d.items():
		rev[v].append(k2)
	(maxim, stack) = (0, [n])
	while stack:
		maxim = max(maxim, stack[max(-len(stack), -1 - k)] - stack[-1])
		if rev[stack[-1]]:
			stack.append(rev[stack[-1]].pop())
		else:
			stack.pop()
	print(maxim)