解题思路

把门按顺序看成下标 $1 \sim n$。

你每经过一扇门，都相当于花 $1$ 秒。 如果在当前正要通过的门处按下按钮，那么接下来连续 $x$ 扇门都视为打开，也就是这一段区间 $[i, i+x-1]$ 内的门都可以直接通过。

因此，问题本质上变成了：

题目内容

你站在一条长度为 $n$ 的走廊起点，沿途有编号 $1$ 到 $n$ 的门，每扇门要么开放（用 $0$ 表示），要么关闭（用 $1$ 表示）。你需要按顺序通过所有门到达出口。

你手中有一个特殊按钮，至多可以使用 $K$ 次。每次按下按钮，会消耗一次使用机会。该次按下的效果是：从你当前正要通过的门开始，在接下来的 $x$ 秒内（即包含当前门在内的连续 $x$ 扇门），所有门都将被视为开放状态。

给定门的状态序列 $a_1,a_2,\dots,a_n\ (a_i \in \{0,1\})$ 和按钮最大发动次数 $K$，请你求出能够通过所有门的最小持续时间 $x$。

输入描述

第一行输入一个整数 $T\ (1 \le T \le 10^3)$，表示测试用例组数；以下共 $T$ 组数据，每组格式如下：

1. 第一行输入两个整数 $n\ (1 \le n \le 2 \times 10^5)$ 和 $K\ (1 \le K \le n)$；
2. 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (a_i \in \{0,1\})$，表示第 $i$ 扇门的状态。

保证所有测试数据中 $\sum n \le 2 \times 10^5$。

输出描述

对于每组测试数据，输出一个整数，表示最小的按钮持续时间 $x$。

样例1

输入

3
4 1
0 1 1 0
8 2
1 1 0 1 1 1 0 1
5 3
0 0 0 0 0

输出

2
4
0

说明

• 第一组：$[0,1,1,0]$ 中只有一个关闭段，长度 $2$，$K=1$，需 $x \ge 2$ 才能覆盖，故最小 $x=2$；
• 第二组：在第一扇门前按下按钮，通过前 $4$ 扇门，再立即按下按钮，通过后 $4$ 扇门，最小 $x=4$；
• 第三组：所有门均开放，无需使用按钮，最小 $x=0$。