Problem 1066. -- D-wxiaoys的歌声

1066: D-wxiaoys的歌声

Time Limit: 1 Sec  Memory Limit: 63 MB
Submit: 2  Solved: 1
[Submit][Status][Web Board]

Description

??????从神秘森林回来后,wsxiaoys爆发了创作的热情。他唱出了一个有n个节拍的歌曲,并知道每个节拍的音量。他想把这些节拍分成小节。每个小节包含相邻的一些节拍,并且每个节拍只能包含在一个小节中。wsxiaoys希望每个小节包含k个节拍。对于每个节拍他要求:每个小节的第一个节拍的音量是都不小于该小节中其他节拍的音量。而且,第一个和最后一个小节可以是不完整的(即只包含1~k-1个节拍)。由于完全达到要求比较困难,wsxiaoys希望,至少有80%的完整小节满足他的要求,并且至少要有一个完整的小节(即包含k个节拍的小节)。
???????于是他向正在编写一个音乐分析软件的wcwswswws求教,由于wcwswswws忙于课业,因此他希望你来帮助wsxiaoys找出满足要求的最小的k(2 <= k <= 10),如果在2~10内找不到这样的k,输出-1。

Input

输入有多组数据。
每组数据两行,第一行为n,表示有n个节拍,第二行n个数,表示节拍音量序列。
1 <= n <= 10000
1 <= 节拍的音量 <= 100

Output

每组数据一行一个数,最小的k或者-1。

Sample Input

9
3 9 3 0 9 3 1 9 11
10
3 9 3 0 9 3 1 9 11 1
13
5 2 5 2 8 6 3 5 5 1 9 0 2
3
1 6 9

Sample Output

3
5
2
-1

HINT

样例1:分割
样例2:分割
样例3:分割
样例4:注意至少要有一个完整小节,因此k=3是不符合要求的

Source

[Submit][Status]