길이 N (2 ≤ N ≤ 10⁶)의 정수 배열 a₁, a₂, …, a_N이 주어집니다 (각 aᵢ는 1 이상 N 이하). 모든 연속 부분 배열(총 N(N+1)/2개)에 대해, 아래의 하위 문제의 정답을 구한 후 그 합을 출력하세요.

하위 문제:

비어 있지 않은 정수 리스트가 주어지면, 리스트의 크기가 정확히 1이 될 때까지 다음 두 연산을 번갈아 수행합니다 (첫 번째 연산부터 시작).

최종 남는 정수의 값이 최대가 되도록 연산을 수행했을 때, 그 최종 정수를 구하는 것이 목표입니다.

예를 들어,

[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가 됩니다.

Min Max Subarrays timer 3s memory 1024MB

Min Max Subarrays 3s 1024MB