CF773E Blog Post Rating

众所周知，博客文章是 Codeforces 平台的重要组成部分。每篇博客有一个随时间变化的全局特征——其社区评分。新创建的博客文章的社区评分为 $0$。Codeforces 用户可以浏览博客页面并对其评分，每次评分可以使社区评分增加 $1$ 或减少 $1$。 我们用如下模型描述 Codeforces 用户的行为。第 $i$ 个用户有其对博客评分的预估值，记为整数 $a_i$。当该用户访问博客页面时，会将他的预估评分与当前社区评分进行比较。如果他的预估评分更高，他会给博客评分 $+1$（社区评分加 $1$）；若预估评分更低，则给评分 $-1$（社区评分减 $1$）；如果两者相等，则该用户不评分（我们称评分为 $0$）。无论如何，评分后该用户就关闭页面，再也不会访问。 现在有一篇新创建的博客文章，初始社区评分为 $0$。共有 $n$ 位 Codeforces 用户（编号为 $1$ 到 $n$），已知每位用户的预估评分 $a_i$。 对于每个 $k$（$1 \leq k \leq n$），需要回答如下问题：设编号从 $1$ 到 $k$ 的用户按某种顺序依次访问博客页面、评分、关闭页面。每一位用户都在前一位用户关闭页面后才打开页面。问在这 $k$ 位用户访问博客页面后，该博客的社区评分可能达到的最大值是多少？

第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$）——Codeforces 用户的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-5 \cdot 10^5 \leq a_i \leq 5 \cdot 10^5$），依次表示每位用户的预估博客评分。

对于每个 $k$ 从 $1$ 到 $n$，输出一个整数，表示在编号从 $1$ 到 $k$ 的用户以某种顺序访问、评分、关闭页面后，博客的社区评分可能达到的最大值。

由 ChatGPT 5 翻译