문제
Wavio란 정수의 수열의 일종이다. 이는 아래와 같은 재미있는 특성을 갖추고 있다.
Wavio인 수열은 홀수의 길이를 가진다. L=2*n+1 (L:길이) 앞의 (n+1)개의 정수는 오름차순 순이다. 뒤의 (n+1)개의 정수는 내림차순 순이다. Wavio를 이루는 수열 안의 인접한 두 개의 정수는 같을 수 없다.
예를 들어 1, 2, 3, 4, 5, 4, 3, 2, 0은 길이 9의 wavio 수열이다. 하지만 1, 2, 3, 4, 5, 4, 3, 2, 2는 wavio 수열이 아니다.
이번에 풀어야할 문제는 정수의 수열이 주어졌을 때, 수열을 이루는 부분 수열 중에서 가장 긴 wavio 수열을 찾는 것이다. 예로 들어서 다음과 같은 정수의 수열이 주어졌다고 하자.
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1
위의 경우에서 가장 긴 wavio 수열은 다음과 같다. : 1 2 3 4 5 4 3 2 1. 따라서 출력해야 하는 길이는 9이다.
입력
첫 번째 줄에는 주어지는 정수 수열의 개수 N(1≤N≤100,000)이 주어진다.
다음 줄에는 N개의 정수로 이루어진 수열이 입력된다. 수열의 숫자의 사이에는 공백이 주어진다.
출력
주어진 정수 수열에서의 가장 긴 wavio 수열의 길이를 출력한다.
예제1
입력
19
1232123432154123221
출력
9
예제2
입력
5
12345
출력
1
출처
UVa 10534