분리자

서로 다른 정수로 이루어진 수열 $A = (a_1, a_2, \ldots)$가 있다. 인덱스 $j$가 다음 두 조건을 만족하면 분리자라고 한다.

• 모든 $k < j$에 대해 $a_k < a_j$,
• 모든 $k > j$에 대해 $a_k > a_j$.

다시 말해, 배열 $A$는 $a_j$보다 작은 원소들, $a_j$ 자신, $a_j$보다 큰 원소들, 이렇게 세 부분으로 나뉜다.

예를 들어 $A = (30, 10, 20, 50, 80, 60, 90)$이라 하자. 분리자는 인덱스 4와 7이며, 각각 값 50과 90에 대응한다.

수열 $A$는 처음에 비어 있다. $A$에 하나씩 덧붙일 원소 $a_1, \ldots, a_n$이 주어진다. 각 $a_i$를 덧붙인 뒤, 현재 수열에 있는 분리자의 개수 $s_i$를 출력한다.

입력 형식은 답을 온라인으로 계산하도록 정해져 있다. $A$에 덧붙일 원소 $a_i$ 대신 수열 $b_i$가 주어진다.

입력은 다음과 같이 처리한다.

빈 수열 $A$에는 분리자가 $s_0 = 0$개 있다.

각 $i = 1$부터 $n$까지 다음을 수행한다.

1. $a_i = (b_i + s_{i-1}) \bmod 10^9$을 계산한다.
2. $a_i$를 수열 $A$에 덧붙인다.
3. 현재 수열 $A$의 분리자 개수 $s_i$를 계산한다.
4. $s_i$를 한 줄에 출력한다.

첫째 줄에 정수 $n$이 주어진다. ($1 \le n \le 10^6$) 이는 처리할 질의의 수이다.

이어서 $n$개의 줄이 주어진다. 이 중 $i$번째 줄에는 정수 $b_i$가 주어진다. ($0 \le b_i \le 10^9 - 1$) $b_i$는 계산할 $a_i$가 모두 서로 다르도록 정해져 있다.

위에서 설명한 대로 $s_1$부터 $s_n$까지 $n$개의 줄에 출력한다.

첫 번째 예제는 문제 지문에 설명되어 있다.

두 번째 예제를 복호화하면 $A = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)$이다.