구슬 정렬

구슬 정렬(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$가 주어질 때, 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$로 나눈 나머지를 출력하세요.