16161번 - 가장 긴 증가하는 팰린드롬 부분수열

문제

팰린드롬 수열이란 앞에서부터 읽을 때와 뒤에서부터 읽을 때 똑같은 수열을 말한다. 수열 {13, 25, 3, 25, 13}, {9, 5, 5, 9}는 팰린드롬이고, {1, 2, 3, 4, 5, 6, 7, 6}, {1, 2, 5, 4, 2}, {1, 1, 3, 2, 4}는 팰린드롬이 아니다.

증가하는 팰린드롬 수열이란 원소들이 바깥에서 팰린드롬 중심으로 갈 수록 값이 증가하는 팰린드롬 수열을 말한다. 수열 {1, 2, 3, 2, 1}, {32, 59, 75, 75, 59, 32}는 증가하는 팰린드롬이고, {3, 2, 1, 2, 3}, {32, 57, 57, 80, 57, 57, 32}, {8, 7, 9, 7, 8}은 증가하는 팰린드롬이 아니다.

주어지는 수열 S에서 인접한 원소들로 구성된 부분수열 중 길이가 가장 긴 증가하는 팰린드롬 부분수열의 길이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 S의 길이 N(1 ≤ N ≤ 10⁵)이 주어진다.

둘째 줄에 수열 S의 i번째 원소를 의미하는 정수 S_i(1 ≤ S_i≤ 10⁹)가 순서대로 공백으로 구분되어 주어진다.

출력

수열 S에서 인접한 원소들로 구성된 부분수열 중 길이가 가장 긴 증가하는 팰린드롬 부분수열의 길이를 출력하라.

제한

힌트