题目描述

长度为\(n\)的序列\(\{a_i\}, i=1,2 \cdots n\)，如果它满足如下条件，就称它为“单峰序列”：
存在某个\(m\)，\(1 < m < n\)，使得：
（1）当\(1 \le k < m\)时，\(a_k < a_{k+1}\)；
（2）当\(m \le k < n\)时，\(a_k > a_{k+1}\)。
给定一个长度为\(N\)的序列\(\{s_i\}, i=1,2 \cdots N\)，求它的最长单峰子序列。“子序列”指的是从原序列中选出若干个数（位置上可以不连续），保持相对位置不变，而构成的新序列。

格式

输入格式

第一行是一个正整数\(N\)；
第二行是\(N\)个正整数\(s_1, s_2 \cdots s_N\)

输出格式

一个正整数，如果存在单峰子序列，输出最长单峰子序列的长度；若不存在，输出-1。

样例1

输入

7
3 7 6 1 4 3 5

输出

5

样例2

输入

7
2 1 3 4 5 6 7

输出

-1

数据规模及限制

时间限制1s，空间限制64MB
共10组测试数据。
测试点#1：\(N \le 10, \phantom{x} a_i \le 10^4\)
测试点#2：\(N \le 10, \phantom{x} a_i \le 10^9\)
测试点#3：\(N \le 200, \phantom{x} a_i \le 10^4\)
测试点#4 ~ #5：\(N \le 200, a_i \le 10^9\)
测试点#6 ~ #7：\(N \le 3000, a_i \le 10^4\)
测试点#8 ~ #10：\(N \le 3000, a_i \le 10^9\)

来源

2017.7 太原五中高一集训
改编自NOIP'04提高组“合唱队形”一题