제3회 디미고 프로그래밍 챌린지 오픈 콘테스트

원소가 모두 다른 수열 A=(a_1,⋯,a_N)에 대해, 수열 A의 점수는 아래와 같이 정의한다.

• i=1,2,⋯,N−1에 대해 a_i<a_{i+1}이면 −를 쓰고, a_i>a_{i+1}이면 +를 종이에 써 길이 N−1의 문자열을 만든다.

• 점수는 만든 문자열에서 같은 기호가 연속되는 구간으로 나눈 뒤, 각 구간의 길이를 제곱해 모두 더한 값으로 정의한다. 즉, 연속된 + 구간과 연속된 − 구간을 각각 하나의 구간으로 보고, 그 길이를 제곱하여 합한 값이다.

예를 들어, A=(7,8,1,3,6,4,2,9)와 같은 경우에는 종이에 쓴 문자열은 +−++−−+이며 여기서 같은 기호가 연속된 구간은 +, −, ++, −−, + 이므로 길이의 제곱의 합인 1^2+1^2+2^2+2^2+1^2=11이 수열 A의 점수다.

순열 A=(a_1,⋯,a_N)에 대한 점수는 A의 모든 부분 수열의 점수 중 최댓값으로 정의한다.

길이 N인 순열이 주어질 때, 순열의 점수를 구해보자.