문제
N개의 산이 일정한 간격으로 일렬로 있고, 각 산의 높이는 h1, h2, …, hn으로 표현된다.
정상에서 서로를 바라보았을 때 그 사이에 두 산의 높이보다 높거나 같은 산이 그 사이를 가로막지 않는 두 산 i, j (i<j)에 대해 반가운 산이라고 한다.
한 개의 산의 높이를 증가시키는 Q개의 업데이트가 주어진다면, 정렬되지 않은 반가운 산인 쌍의 총 개수를 매 업데이트마다 출력하자.
입력
첫 번째 줄에 산의 개수 N이 주어진다 (1≤N≤2000).
두 번째 줄에 N개의 정수 h1, h2, …, hn이 입력된다 (각 i에 대해, 0≤hi≤109).
세 번째 줄에 업데이트의 수 Q가 입력된다 (1≤Q≤2000).
네 번째 줄부터 Q줄에 걸쳐 산의 인덱스 x와 증가하는 높이 y가 입력된다. (1≤x≤N, 1≤y)
이때, 높이가 증가된 산의 높이는 최대 109임이 보장된다.
출력
Q 줄에 걸쳐 정렬되지 않은 반가운 산인 쌍의 총 개수를 출력하시오.
예제
5
2 4 3 1 5
3
4 3
1 3
3 2
7
10
7
힌트
출처
USACO 2022 December Gold
로그인해야 코드를 작성할 수 있어요.