Slavic 有一个长度为 $$$n$$$ 的数组,仅由零和一组成。在一次操作中,他删除数组的第一个或最后一个元素。
Slavic 最少需要执行多少次操作才能使执行完所有操作后数组的总和等于 $$$s$$$?如果经过任意次数的运算仍无法获得总和$$$s$$$,则应输出-1。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$s$$$ ($$$1 \leq n, s \leq 2 \cdot 10^5$$$) - 数组的长度和所需的元素总和。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$0 \leq a_i \leq 1$$$) — 数组的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 使数组总和等于 $$$s$$$ 所需的最少操作量,如果无法获得总和为 $$$s$$$ 的数组,则输出 -1。
示例
输入 #1
7 3 1 1 0 0 3 1 1 1 0 9 3 0 1 0 1 1 1 0 0 1 6 4 1 1 1 1 1 1 5 1 0 0 1 1 0 16 2 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 6 3 1 0 1 0 0 0
输出 #1
0 1 3 2 2 7 -1
注意
在第一个测试用例中,从一开始整个数组的总和就是$$$1$$$,因此我们不必进行任何操作。
在第二个测试用例中,数组的总和为 $$$2$$$,我们希望它等于 $$$1$$$,因此我们应该删除第一个元素。该数组变为 $$$[1, 0]$$$,其总和等于 $$$1$$$。
在第三个测试用例中,数组的总和是 $$$5$$$,我们需要它是 $$$3$$$。我们可以通过删除前两个元素和最后一个元素,总共进行三个操作来获得这样的总和。该数组变为 $$$[0, 1, 1, 1, 0, 0]$$$,其总和等于 $$$3$$$。