Statement
길이가 인 수열 의 점수는 다음과 같이 정의된다.
길이가 인 수열 이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.
- : 를 수행한다.
- : 구간 에 속한 원소들을 가지 색깔 중 하나로 칠한다. 각 색깔은 최소 한 번 이상 사용되어야 한다. 색깔이 인 원소들로 이루어진 부분 수열을 라고 할 때, 가능한 모든 색칠 방법 중 다음 수식의 최댓값을 출력한다.
Input
첫째 줄에 수열의 크기 이 주어진다.
둘째 줄에는 이 주어진다.
셋째 줄에는 쿼리의 개수 이 주어진다.
넷째 줄부터 개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.
Output
2번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.
Subtasks
Samples
Sample 1
Input
3
-2 -8 12
2
2 1 2 1
2 1 3 1
Output
16
-104
Sample 2
Input
6
3 -1 4 -5 -9 -2
4
2 1 4 2
1 3 6
1 4 5
2 2 6 3
Output
17
48