English · Original
Chinese · Translation
Formal · Original
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 _a__i_. 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 _a__i_ 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
The first line contains a single integer _n_ (1 ≤ _n_ ≤ 5·105) — the number of Codeforces users.
The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ ( - 5·105 ≤ _a__i_ ≤ 5·105) — estimated blog post ratings for users in order from 1 to _n_.
## Output
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.
[samples]
众所周知，博客文章是 Codeforces 平台的重要组成部分。每篇博客文章都有一个随时间变化的全局特征——其 #cf_span(class=[tex-font-style-underline], body=[社区评分])。新创建的博客文章的社区评分为 0。Codeforces 用户可以访问博客文章页面并对其进行评分，使其社区评分增加 +1 或减少 -1。
考虑以下 Codeforces 用户行为模型。第 #cf_span[i]-th 个用户有自己的 #cf_span(class=[tex-font-style-underline], body=[估计博客评分])，记为整数 #cf_span[ai]。当一个用户访问博客页面时，他会将自己的估计评分与社区评分进行比较。如果他的估计评分更高，他会给出 +1 评分（从而使博客的社区评分增加 1）；如果他的估计评分更低，他会给出 -1 评分（使社区评分减少 1）；如果估计评分与社区评分相等，用户不会对该博客评分（此时我们称用户评分为 0）。无论如何，在此操作后，用户会关闭博客页面，且再也不会打开它。
考虑一篇新创建的博客文章，其初始社区评分为 0。对于编号从 1 到 #cf_span[n] 的 #cf_span[n] 个 Codeforces 用户，已知他们的估计博客评分 #cf_span[ai]。
对于每个 #cf_span[k]（从 1 到 #cf_span[n]），提出如下问题：令索引从 1 到 #cf_span[k] 的用户，以某种顺序访问博客页面，进行评分并关闭页面。每个用户仅在前一个用户关闭页面后才打开博客。在这些 #cf_span[k] 次访问之后，博客的社区评分最大可能值是多少？
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 5·105]) —— Codeforces 用户的数量。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 5·105 ≤ ai ≤ 5·105]) —— 按用户 1 到 #cf_span[n] 顺序给出的估计博客评分。
对于每个 #cf_span[k] 从 1 到 #cf_span[n]，输出一个整数，表示在索引为 1 到 #cf_span[k] 的用户以某种顺序访问博客页面、评分并关闭页面后，博客可能达到的最大社区评分。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 5·105]) —— Codeforces 用户的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[ - 5·105 ≤ ai ≤ 5·105]) —— 按用户 1 到 #cf_span[n] 顺序给出的估计博客评分。
## Output
对于每个 #cf_span[k] 从 1 到 #cf_span[n]，输出一个整数，表示在索引为 1 到 #cf_span[k] 的用户以某种顺序访问博客页面、评分并关闭页面后，博客可能达到的最大社区评分。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of users.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ a_i \in \mathbb{Z} $ is the estimated rating of user $ i $.
**Constraints**
$ 1 \leq n \leq 5 \cdot 10^5 $,
$ -5 \cdot 10^5 \leq a_i \leq 5 \cdot 10^5 $ for all $ i \in \{1, \dots, n\} $.
**Objective**
For each $ k \in \{1, \dots, n\} $, let $ S_k \subseteq \{a_1, \dots, a_k\} $ be a multiset of the first $ k $ estimated ratings.
Define the **community rating** after processing $ S_k $ in some order as:
$$
R(S_k) = \sum_{i=1}^k r_i, \quad \text{where} \quad r_i =
\begin{cases}
+1 & \text{if } a_i > \text{current rating}, \\
-1 & \text{if } a_i < \text{current rating}, \\
0 & \text{if } a_i = \text{current rating}.
\end{cases}
$$
The **current rating** evolves sequentially: starts at 0, and each $ r_i $ updates it additively.
Find, for each $ k $, the **maximum possible value** of $ R(S_k) $ over all permutations of $ S_k $.
API Response (JSON)
{
"problem": {
"name": "E. Blog Post Rating",
"description": {
"content": "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 communi",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF773E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 communi...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "众所周知，博客文章是 Codeforces 平台的重要组成部分。每篇博客文章都有一个随时间变化的全局特征——其 #cf_span(class=[tex-font-style-underline], body=[社区评分])。新创建的博客文章的社区评分为 0。Codeforces 用户可以访问博客文章页面并对其进行评分，使其社区评分增加 +1 或减少 -1。\n\n考虑以下 Codeforces 用户行...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of users. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ a_i \\in \\mathbb{Z} $ is the estimated rating of user $ i $....",
"is_translate": false,
"language": "Formal"
}
]
}