问题描述

从神秘森林回来后，wsxiaoys 爆发了创作的热情。他唱出了一个有 $n$ 个节拍的歌曲，并知道每个节拍的音量。他想把这些节拍分成小节。每个小节包含相邻的一些节拍，并且每个节拍只能包含在一个小节中。wsxiaoys 希望每个小节包含 $k$ 个节拍。对于每个节拍他要求：每个小节的第一个节拍的音量是都不小于该小节中其他节拍的音量。而且，第一个和最后一个小节可以是不完整的（即只包含 $1 \sim k-1$ 个节拍）。由于完全达到要求比较困难，wsxiaoys 希望，至少有 $80\%$ 的完整小节满足他的要求，并且至少要有一个完整的小节（即包含 $k$ 个节拍的小节）。

于是他向正在编写一个音乐分析软件的 wcwswswws 求教，由于 wcwswswws 忙于课业，因此他希望你来帮助 wsxiaoys 找出满足要求的最小的 $k$（$2 \leq k \leq 10$），如果在 $2 \sim 10$ 内找不到这样的 $k$，输出 $-1$。

输入格式

输入有多组数据。

每组数据两行，第一行为 $n$，表示有 $n$ 个节拍，第二行 $n$ 个数，表示节拍音量序列。

$1 \leq n \leq 10000$

$1 \leq$ 节拍的音量 $\leq 100$

输出格式

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

样例输入

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

样例输出

3
5
2
-1

提示

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