https://codeforces.com/contest/1556/problem/C
시간 1초, 메모리 256MB

input :

• t (1 ≤ t ≤ 1000)
• c1, c2, …, cn (1 ≤ ci ≤ 109)

output :

• Output a single integer — the total number of subsegments of the original bracket sequence, which are regular bracket sequences.
  올바른 괄호 식을 만들 수 있는 개수를 출력하시오.

조건 :

• 괄호를 그냥 나타내면 너무 커서 숫자로 입력을 해준다. 홀수 인덱스의 경우 '('의 개수, 짝수 인덱스의 경우 ')'의 개수를 나타낸다.

• 연속적인 부분배열에서 만들 수 있는 올바른 괄호 식의 개수를 모두 계산해 주기를 원한다.

너무 오래 걸렸다. 아직도 사실 어렵다.
가장 먼저 생각해 둘것은 앞에서 부터 뒤로 모든 괄호 식을 만들며 움직이는 것은 오래 걸리기도 할 뿐더러 놓치는 부분이 많이 발생한다.
현재를 기준으로 이전에 만들어둔 괄호들을 체크 하는 것이 편하다.

일단 각 괄호를 확인할 때 우리는 쌍으로 확인할 거다.

그러면 그 때 만들 수 있는 올바른 괄호식의 개수를 확인할 수 있는데 이 때 두 가지 경우가 있다.

1. 여는 괄호가 남는 경우 -> 닫는 괄호의 개수가 올바른 괄호식이 된다.
2. 닫는 괄호가 이전의 여는 괄호에 맞는 경우 -> 현재 남은 여는 괄호 + 닫는 괄호 - 맨 처음의 괄호가 닫힐 때 남았던 여는 괄호의 개수

스택 초기화

맨 처음 스택을 만들 었을 때는 그 이전에 존재하는 괄호 식이 없으니까 [0, 0]을 저장한다.
[0]번째에는 이전에 존재했던 여는 괄호의 수
[1]번째에는 이 괄호 식을 붙이면 몇 개의 올바른 식을 만 들 수 있는지를 저장한다.

그러면 반복문이 돌 때 남은 여는 괄호의 수는 opne - close의 수로 계산 할 수 있다.
이 때 음수여도 그냥 둔다. 음수의 경우에는 닫히고 나서 더 이상 새로운 괄호 식을 붙일 수 없다고 보면 된다.

그러니까 새로운 괄호식이 들어와야 한 다는 것이고 이럴 때에 [cur_open, 0]이 추가된다.

현재 기준으로 이전의 괄호식 붙이기

현재를 기준으로 이전에 존재했던 괄호들을 확인 할 때 이전의 [0]이 cur_open보다 크다는 것은
닫는 괄호가 더 늘어나 이걸 채워 준것이라고 볼 수 있다.
그래서 이 괄호식을 통해 늘어나는 값을 정답에 더해준다.

만약 값이 동일하다면?
얘는 계속 추가를 할 수 있다. open, close가 동일하고, 그 뒤의 괄호 식도 그런 경우에는 이 두개를 추가함 으로써 올바른 괄호식을 2개를 만들 수 있으니까 이 경우도 생각해야 한다.

새로운 괄호식

이전에 존재하던 괄호식에 더 이상 괄호들을 붙일 수 없다 -> 스택이 비었다. 새롭게 추가
위의 경우가 아니라면 [cur_open, 1]을 추가한다. 현재 열린 괄호의 개수를 기록하고 나중에 비교하는 것이다.

위에서 닫는 괄호를 통해서 개수를 세아린다. 이 것에서
현재의 괄호식을 만들 때 그 이전에 남아있는 괄호식들까지 포함 할 수 있는지를 확인한다.
그리고 그 이외의 것을 찾을 때는 스택을 돌아가면서 이 괄호식 자체를 추가할 수 있는지를 보는 것이다.

import sys

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))

ans, cur_open = 0, 0
s = [[0, 0]]

for i in range(0, n, 2):
    if i + 1 >= n:
        continue

    open_bracket = data[i]
    close_bracket = data[i + 1]

    cur_open += open_bracket - close_bracket
    ans += min(close_bracket, cur_open + close_bracket - s[0][0])
    while s and s[-1][0] > cur_open:
        ans += s[-1][1]
        s.pop()

    if s and s[-1][0] == cur_open:
        ans += s[-1][1]
        s[-1][1] += 1
    else:
        if s:
            s.append([cur_open, 1])
        else:
            s.append([cur_open, 0])

print(ans)