길이 n 짜리 수열 a[1] ~ a[n] 이 있을 때, "예쁜 수열" 은 아래와 같이 정의한다.

" 1 ≤ i ≤ n 인 모든 i 에 대해, a[i] ≥ i 이면, 수열 a 는 예쁜 수열이다. "

예를 들어, [2, 5, 4] 는 예쁜 수열이다. a[1] ≥ 1, a[2] ≥ 2, a[3] ≥ 3 이 모두 성립하기 때문이다.

[5, 1, 4] 는 예쁜 수열이 아니다. a[2] ≥ 2 가 성립하지 않기 때문이다.

자연수로 구성된 길이 N 수열이 입력된다.

우리의 목표는, 모든 ‘연속 부분 수열’ 중 예쁜 수열의 개수를 구하는 것이다.

예를 들어, [2, 4, 2, 3] 의 모든 연속 부분 수열을 나열하면

[2], [4], [2], [3]

[2, 4], [4, 2], [2, 3]

[2, 4, 2], [4, 2, 3]

[2, 4, 2, 3] 으로 총 10개다.

이 중 예쁜 수열은

[2], [4], [2], [3], [2, 4], [4, 2], [2, 3], [4, 2, 3] 으로 8개다.

단, 우리를 방해하는 악마가 Q 마리 있다.

각 악마는, 1 ≤ x ≤ N 인 x 를 하나 정해서, 입력 수열의 x 번째 수를 강제로 p 로 바꾼다.

즉, a[x] = p 가 된다.

각 악마의 방해 공작 후, 연속 부분 수열 중 예쁜 수열의 개수를 출력하자.

모든 악마는 서로 독립적이다.

즉, 한 악마의 방해 공작 후, 수열은 다시 처음 상태로 돌아간다. 그 후, 다음 악마의 방해 공작이 시작된다.

악마와 예쁜 수열 timer 3s memory 512MB

악마와 예쁜 수열 3s 512MB