농부 존은 N마리의 소를 가지고 있고 (2 ≤ N ≤ 5⋅10^6), 소들의 게으름을 이용하여 길이가 N인 음수가 아닌 정수 배열 A를 정렬하려고 한다. 존은 무거운 상자가 많이 있어서 소들을 일렬로 세우고, 소 i+1이 소 i 뒤에 있도록 했다. 그리고 소 i에게 ai개의 상자를 주었다 (0 ≤ ai).

소들은 본래 게을러서 항상 자기 일을 다른 소에게 떠넘기려 한다. 소 1부터 N-1까지 순서대로 각 소는 뒤에 있는 소를 본다. 만약 소 i가 소 i+1보다 엄격하게 더 많은 상자를 가지고 있다면, 소 i는 이를 "불공평하다"고 생각하고 자신의 상자 하나를 소 i+1에게 넘겨준다. 이 과정은 모든 소들이 만족할 때까지 반복된다.

이후 존은 각 소 i가 가지고 있는 상자의 개수 bi를 기록하여 이 값들로 배열 B를 만든다. 만약 B가 A를 정렬한 배열과 같다면 존은 만족할 것이다. 하지만 존은 A 배열에서 단 Q개(2 ≤ Q ≤ min(N, 100))의 값만을 기억하고 있다. 다행히도 이 값들 중에는 첫 번째와 마지막 소에게 줄 예정이었던 상자의 개수가 포함되어 있다. 존이 기억하고 있는 값들은 ci vi의 형태로 주어지며 이는 aci = vi임을 나타낸다 (1 ≤ ci ≤ N, 1 ≤ vi ≤ 10^9). 빠진 값들을 채워서 존이 만족할 수 있는 방법의 수를 mod 10^9+7로 구하라.

#8422 upload 1 done - how_to_reg -

Lazy Sort timer 1s memory 1024MB

#8422

Lazy Sort 1s 1024MB