27518번 - 구슬 정렬 (Hard)

문제

구슬 정렬 (Bead Sort 또는 Gravity Sort)는 구슬을 지면에 수직인 막대에 끼운 뒤 떨어뜨리는 방식으로 양의 정수로 구성된 배열을 정렬하는 방법입니다. 이 방식을 컴퓨터에서 구현하기에는 공간 복잡도와 같은 면에서 많은 어려움이 있으나, 현실과 같은 물리적 모델에서 대략적으로 $O(\sqrt{n})$의 시간 복잡도를 보여준다고 알려져 있습니다. 구슬 정렬은 정확히 다음과 같은 방식으로 진행됩니다.

1. 수열에서 가장 큰 수의 값이 $m$일 때, 총 $m$개의 막대를 준비합니다. 그 뒤 각 막대에 1ドル$번부터 $m$번까지 번호를 붙입니다. 처음에 막대는 일렬로 눕혀 놓습니다.
2. 각 막대를 총 $n$칸으로 나누되, 한 칸의 길이는 구슬의 지름과 같게 합니다. 이 시점부터 "$x$번째 막대의 $y$번째 칸"을 $(x,y)$로 표기합니다.
3. 수열의 각 원소 $a_i$에 대해, $(1,i)$부터 $(a_i,i)$까지 구슬을 총 $a_i$개 끼웁니다.
4. 모든 막대를 1ドル$번 칸이 위로 가도록 동시에 지면에 수직으로 세우면 구슬이 중력의 영향을 받아 번호가 더 큰 칸을 향해 떨어집니다. 그 뒤 위쪽부터 $i$번째 칸에 위치한 구슬의 개수를 읽으면 정렬된 배열의 원소들과 일치합니다.

이러한 과정에 따라 구슬 정렬은 총 $\displaystyle{\sum _i{a_i}}$개의 구슬을 사용합니다. 양의 정수로 구성된 배열 $a$에 대해 구슬 정렬을 수행할 때, $\displaystyle{\sum _i{a_i}}$개의 구슬 모두에 대해 이동한 거리의 합에 해당하는 칸의 개수를 $f(a)$라고 정의합시다. 길이 $n$의 배열 $b_i$가 주어질 때, 길이가 1ドル$ 이상 $n$ 이하인 모든 $i$에 대해 $b$의 $i$번째 접두사 $a_i=[b_1, b_2, \cdots b_i]$에 대해 각각 $f(a_i)$를 구해 출력하세요. 정답이 클 수 있으니 1ドル ,円 000 ,円 000 ,円 007$로 나눈 나머지를 출력하세요.

입력

첫 번째 줄에 배열의 길이 $n$ (1ドル \le n \le 2 \times 10^5$)이 주어집니다.

두 번째 줄에 배열의 각 원소 $b_1$부터 $b_n$까지 총 $n$개의 양의 정수가 공백으로 분리되어 주어집니다. (0ドル < b_i \le 10^9$)

출력

총 $n$개의 줄에 문제의 정답을 각각 출력하세요. $i$번째 줄에는 $f(a_i)$에 해당하는 값을 출력해야 합니다. 정답이 클 수 있으니 1ドル ,円 000 ,円 000 ,円 007$로 나눈 나머지를 출력하세요.

제한

힌트