문제
길이 N (2 ≤ N ≤ 10⁶)의 정수 배열 a₁, a₂, …, a_N이 주어집니다 (각 aᵢ는 1 이상 N 이하). 모든 연속 부분 배열(총 N(N+1)/2개)에 대해, 아래의 하위 문제의 정답을 구한 후 그 합을 출력하세요.
하위 문제:
비어 있지 않은 정수 리스트가 주어지면, 리스트의 크기가 정확히 1이 될 때까지 다음 두 연산을 번갈아 수행합니다 (첫 번째 연산부터 시작).
연산 1: 리스트에서 인접한 두 정수를 그 둘 중 최솟값으로 대체합니다.
연산 2: 리스트에서 인접한 두 정수를 그 둘 중 최댓값으로 대체합니다.
최종 남는 정수의 값이 최대가 되도록 연산을 수행했을 때, 그 최종 정수를 구하는 것이 목표입니다.
예를 들어,
[4, 10, 3]의 경우:
첫 번째 연산에서 (10, 3)을 min(10, 3)=3으로 대체 → [4, 3]
두 번째 연산에서 (4, 3)을 max(4, 3)=4로 대체 → [4]
[3, 4, 10]의 경우:
첫 번째 연산에서 (4, 10)을 min(4, 10)=4로 대체 → [3, 4]
두 번째 연산에서 (3, 4)을 max(3, 4)=4로 대체 → [4]
따라서 첫 번째 경우의 최종 정수는 4, 두 번째 경우에는 4가 됩니다.
입력
첫 번째 줄에 정수 N이 주어집니다.
두 번째 줄에 N개의 정수 a₁, a₂, …, a_N이 공백으로 구분되어 주어집니다.
출력
모든 연속 부분 배열에 대해 하위 문제의 정답을 구한 후, 그 합을 출력합니다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | |
| #2 | 20점 | |
| #3 | 30점 | |
| #4 | 40점 | 추가 제약 없음 |
예제1
2
2 1
4
부분 배열별로 하위 문제의 정답은 다음과 같습니다:
[2] → 최종 정수 2
[1] → 최종 정수 1
[2, 1] → 최종 정수 1
따라서 합은 2 + 1 + 1 = 4.
예제2
3
3 1 3
12
예제3
4
2 4 1 3
22
예를 들어, 전체 배열 [2, 4, 1, 3]의 경우:
첫 번째 연산에서 (1, 3)을 대체 → [2, 4, 1]
두 번째 연산에서 (4, 1)을 대체 → [2, 4]
세 번째 연산에서 (2, 4)을 대체 → 최종 정수 2
최적의 연산 순서를 통해 최종 정수가 2가 되고, 모든 부분 배열에 대해 구한 정답들의 합이 22가 됩니다.