CF818F Level Generation

Ivan 正在开发他自己的电脑游戏。现在他需要为他的游戏设计一些关卡。首先，对于每一关，他需要绘制一个表示该关卡结构的图。 Ivan 决定，每一关的图中要恰好有 $n_i$ 个顶点，并且边必须是双向的。在构建图时，Ivan 对一种特殊的边很感兴趣，这些边被称为桥。对于两个顶点 $u$ 和 $v$ 之间的边，如果该边在所有 $u$ 到 $v$ 的路径上都存在（并且删除该边后 $u$ 和 $v$ 会处于不同的连通块），那么这条边被称为桥。对于每一关，Ivan 想要构造一个图，其中至少一半的边都是桥，同时他还希望每个图中的边数尽可能多。 因此，Ivan 给你的任务是：给定 $q$ 个数 $n_1, n_2, ..., n_q$，对于每个 $i$，请你回答：在至少一半的边是桥的情况下，具有 $n_i$ 个顶点的图最多可以有多少条边。注意，图中不能有重边或自环。

输入文件的第一行包含一个正整数 $q$（$1 \leq q \leq 100000$），表示 Ivan 需要构造的图的数量。 接下来有 $q$ 行，第 $i$ 行包含一个正整数 $n_i$（$1 \leq n_i \leq 2·10^9$），表示第 $i$ 个图中的顶点数。 注意，在 Hack 数据中你需要使用 $q=1$。

输出 $q$ 个数字，第 $i$ 个数字表示第 $i$ 个图中在至少一半的边是桥的情况下，能够拥有的最大边数。

在第一个例子中，可以构造如下的图： 1. $1-2$，$1-3$； 2. $1-2$，$1-3$，$2-4$； 3. $1-2$，$1-3$，$2-3$，$1-4$，$2-5$，$3-6$。 由 ChatGPT 5 翻译