蒟蒻求助（违规紫衫

问题描述： 
学校想在广告板上贴不同的宣传单（宣传单长度不一定相同），宣传单与广告板
宽度相同，他想要在长度为n个单位的广告板上张贴至多n张宣传单，如果选择
第i张贴宣传单时需要满足： 
 第i张必须要覆盖掉广告板的第i个位置； 
 宣传单不能互相重叠，但是可以紧贴。 
小码想要知道按照要求，他至少需要贴几张宣传单才能将广告板贴满。请你用编
程的方式解决这个问题。 
输入描述: 
第一行输入测试组数t； 
每组测试数据的第一行输入一个整数n代表广告板的长度（同时也代表了宣传单
的张数），第二行输入n个整数表示每一张宣传单的长度。 
输出描述: 
输出t行数据，每行包含一个整数，代表小码至少需要贴的宣传单的数量；如果
无解，直接输出−1。 
输入样例1：   
3 
4 
1 2 2 3 
3 
2 2 2 
4 
5 6 1 3  
输出样例1： 
2 -1 -1 
解释：   
对于第一组测试数据，有两种合法的选择方式，都需要两张： 
 贴第一、四张宣传单； 
 贴第二、三张宣传单； 
对于第二组测试数据，无论怎么张贴都会有重叠部分，故输出-1。 
对于第三组测试数据，可以用1，3覆盖，但是1是第4个数，不能满足第i个
覆盖掉第i个位置，故输出-1。 
数据规模和约定： 
1<=t<=30;1<=ai<=n<=5000。