Blog Post Rating
Contest: VK Cup 2017 - Round 3
Difficulty rating: 3000
Tags: data structures, sortings

It's well-known that blog posts are an important part of Codeforces platform. Every blog post has a global characteristic changing over time — its community rating. A newly created blog post's community rating is 0. Codeforces users may visit the blog post page and rate it, changing its community rating by +1 or -1.

Consider the following model of Codeforces users' behavior. The i-th user has his own estimated blog post rating denoted by an integer ai. When a user visits a blog post page, he compares his estimated blog post rating to its community rating. If his estimated rating is higher, he rates the blog post with +1 (thus, the blog post's community rating increases by 1). If his estimated rating is lower, he rates the blog post with -1 (decreasing its community rating by 1). If the estimated rating and the community rating are equal, user doesn't rate the blog post at all (in this case we'll say that user rates the blog post for 0). In any case, after this procedure user closes the blog post page and never opens it again.

Consider a newly created blog post with the initial community rating of 0. For each of n Codeforces users, numbered from 1 to n, his estimated blog post rating ai is known.

For each k from 1 to n, inclusive, the following question is asked. Let users with indices from 1 to k, in some order, visit the blog post page, rate the blog post and close the page. Each user opens the blog post only after the previous user closes it. What could be the maximum possible community rating of the blog post after these k visits?

Input format:
The first line contains a single integer n (1 ≤ n ≤ 5·105) — the number of Codeforces users.

The second line contains n integers a1, a2, ..., an ( - 5·105 ≤ ai ≤ 5·105) — estimated blog post ratings for users in order from 1 to n.

Output format:
For each k from 1 to n, output a single integer equal to the maximum possible community rating of the blog post after users with indices from 1 to k, in some order, visit the blog post page, rate the blog post, and close the page.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
4
2 0 2 2

Example output:
1
1
2
2

Example input:
7
2 -3 -2 5 0 -3 1

Example output:
1
0
-1
0
1
1
2

Editorial:
There are several different solutions to this problem, I'll describe one of them.
First, we have to determine the optimal rating order for a set of users. Using an exchange argument, it can be shown that to maximize the final community rating the users should rate the blog post in non-decreasing order of their estimated ratings. Indeed, consider an optimal rating order, consider two users with estimated ratings x and y next to each other in this order, and assume that x > y. Let's denote the community rating before these two users rate the blog post by a. Then here is what happens if these two users rate this blog post in the current and the reverse order:
We can see that the x, y order is never better than y, x. That means we can swap these two users in the order and the result won't become worse. We can continue swapping all such pairs of users until we obtain a non-decreasing order.
Now, suppose users with estimated ratings b1 ≤ b2 ≤ ... ≤ bm rate a newly created blog post. For some x, the first x users will rate it with -1. It can be seen that the following property will hold for the rest of the users — their estimated ratings will not be lower than the community rating of the blog post at the moment of viewing the page. Thus, all remaining users will rate the blog post with +1 or 0.
Let's sort all users according to their estimated rating, and maintain a segment tree which contains, for each user in this order, the difference between his estimated rating and the community rating after his view. Initially, all users are inactive and it looks like they rate the blog post with 0. Then, we'll make users active one by one in order of input. We'll also maintain three sets of active users — those who rate the blog post with +1, 0 and -1, respectively.
To make a user active, first we find how he rates the blog post. Then, there are three cases:
• If he rates the blog post for 0, there is no need to do anything else.
• If he rates the blog post for -1, the rightmost -1 might change to 0. If it does, we are done. Otherwise, the community rating before users in the "+1 and 0" group has decreased by 1. Thus, the leftmost 0 (if it exists) changes to +1, and we're done.
• If he rates the blog post for +1, then either there's a user to the right of him whose value in the segment tree becomes negative, in which case the leftmost of these users now rates the blog post for 0 instead of +1, or there's no such user, in which case nothing else changes.
All operations above can be performed using queries to our sets of users and segment tree. For example, when a user appears who rated the blog post with +1, we have to insert him into the +1 set and make a query to the segment tree to decrease the value by 1 in the range from this user to the last user. The answer — that is, the maximum possible community rating after the first k users — is the size of the +1 set minus the size of the -1 set.