给定一个长度为 的序列 ,你每次可以做如下操作: 选择两个不同的下标 ,令 。 请问最少操作多少次,可以使得序列中恰好有 个正数,如果无法做到请你输出 -1。
输入描述:
本题有多组测试数据第一行输入一个整数 ,表述数据组数。对于每组测试数据:第一行输入两个整数 。第二行输入 个整数 。保证 。


输出描述:
对于每组测试数据,输出最少操作多次可以使得序列中恰好有 个正数,如果无法做到请你输出 -1。
示例1

输入

2
4 2
2 4 3 -1
4 4
-1 -3 -4 -5

输出

1
-1

说明

对于第一组测试数据,可以选择 i=3,j=4,令 A_{3} = A_{3} × A_{4} = 3 × (-1) = -3,此时序列中正数个数变为 2 个,故最少操作 1 次。 

对于第二组测试数据,初始所有数都为负数,通过操作至多变成 3 个正数,无法达到 4 个,输出 -1。
加载中...