English · Original
Chinese · Translation
Formal · Original
Ivan is developing his own computer game. Now he tries to create some levels for his game. But firstly for each level he needs to draw a graph representing the structure of the level.
Ivan decided that there should be exactly _n__i_ vertices in the graph representing level _i_, and the edges have to be bidirectional. When constructing the graph, Ivan is interested in special edges called _bridges_. An edge between two vertices _u_ and _v_ is called a _bridge_ if this edge belongs to every path between _u_ and _v_ (and these vertices will belong to different connected components if we delete this edge). For each level Ivan wants to construct a graph where at least half of the edges are _bridges_. He also wants to maximize the number of edges in each constructed graph.
So the task Ivan gave you is: given _q_ numbers _n_1, _n_2, ..., _n__q_, for each _i_ tell the maximum number of edges in a graph with _n__i_ vertices, if at least half of the edges are _bridges_. **Note that the graphs cannot contain multiple edges or self-loops**.
## Input
The first line of input file contains a positive integer _q_ (1 ≤ _q_ ≤ 100 000) — the number of graphs Ivan needs to construct.
Then _q_ lines follow, _i_\-th line contains one positive integer _n__i_ (1 ≤ _n__i_ ≤ 2·109) — the number of vertices in _i_\-th graph.
_Note that in hacks you have to use _q_ = 1._
## Output
Output _q_ numbers, _i_\-th of them must be equal to the maximum number of edges in _i_\-th graph.
[samples]
## Note
In the first example it is possible to construct these graphs:
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.
Ivan 正在开发自己的电脑游戏。现在他试图为游戏创建一些关卡。但首先，他需要为每个关卡绘制一个表示关卡结构的图。
Ivan 决定，表示第 #cf_span[i] 个关卡的图中应恰好有 #cf_span[ni] 个顶点，且边必须是双向的。在构造图时，Ivan 对一种称为 _桥_ 的特殊边感兴趣。连接两个顶点 #cf_span[u] 和 #cf_span[v] 的边被称为 _桥_，当且仅当这条边属于 #cf_span[u] 和 #cf_span[v] 之间的每一条路径（如果我们删除这条边，这两个顶点将属于不同的连通分量）。对于每个关卡，Ivan 希望构造一个图，使得至少一半的边是 _桥_。他还希望最大化每个构造图中的边数。
因此，Ivan 给你的任务是：给定 #cf_span[q] 个数 #cf_span[n1, n2, ..., nq]，对于每个 #cf_span[i]，求出在具有 #cf_span[ni] 个顶点的图中，满足至少一半的边是 _桥_ 的前提下，所能拥有的最大边数。*注意图中不能包含多重边或自环*。
输入文件的第一行包含一个正整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 100 000]) —— Ivan 需要构造的图的数量。
接下来 #cf_span[q] 行，第 #cf_span[i] 行包含一个正整数 #cf_span[ni] (#cf_span[1 ≤ ni ≤ 2·109]) —— 第 #cf_span[i] 个图的顶点数。
_注意：在 Hack 中，你必须使用 #cf_span[q = 1]_。
输出 #cf_span[q] 个数，第 #cf_span[i] 个数必须等于第 #cf_span[i] 个图的最大边数。
## Input
输入文件的第一行包含一个正整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 100 000]) —— Ivan 需要构造的图的数量。接下来 #cf_span[q] 行，第 #cf_span[i] 行包含一个正整数 #cf_span[ni] (#cf_span[1 ≤ ni ≤ 2·109]) —— 第 #cf_span[i] 个图的顶点数。_注意：在 Hack 中，你必须使用 #cf_span[q = 1]_。
## Output
输出 #cf_span[q] 个数，第 #cf_span[i] 个数必须等于第 #cf_span[i] 个图的最大边数。
[samples]
## Note
在第一个例子中，可以构造以下图： #cf_span[1 - 2], #cf_span[1 - 3]; #cf_span[1 - 2], #cf_span[1 - 3], #cf_span[2 - 4]; #cf_span[1 - 2], #cf_span[1 - 3], #cf_span[2 - 3], #cf_span[1 - 4], #cf_span[2 - 5], #cf_span[3 - 6].
**Definitions**
Let $ q \in \mathbb{Z}^+ $ be the number of graphs.
For each $ i \in \{1, \dots, q\} $, let $ n_i \in \mathbb{Z}^+ $ be the number of vertices in graph $ i $.
**Constraints**
1. $ 1 \le q \le 100{,}000 $
2. $ 1 \le n_i \le 2 \cdot 10^9 $ for all $ i \in \{1, \dots, q\} $
3. Graphs are simple (no self-loops, no multiple edges).
4. At least half of the edges must be bridges.
**Objective**
For each $ n_i $, find the maximum number of edges $ e_i $ in a simple graph with $ n_i $ vertices such that at least half of the edges are bridges.
Let $ e_i $ be the total number of edges and $ b_i $ the number of bridges. Then:
$$
b_i \ge \frac{e_i}{2}, \quad \text{and} \quad e_i \text{ is maximized}.
$$
API Response (JSON)
{
"problem": {
"name": "F. Level Generation",
"description": {
"content": "Ivan is developing his own computer game. Now he tries to create some levels for his game. But firstly for each level he needs to draw a graph representing the structure of the level. Ivan decided th",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF818F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Ivan is developing his own computer game. Now he tries to create some levels for his game. But firstly for each level he needs to draw a graph representing the structure of the level.\n\nIvan decided th...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Ivan 正在开发自己的电脑游戏。现在他试图为游戏创建一些关卡。但首先，他需要为每个关卡绘制一个表示关卡结构的图。\n\nIvan 决定，表示第 #cf_span[i] 个关卡的图中应恰好有 #cf_span[ni] 个顶点，且边必须是双向的。在构造图时，Ivan 对一种称为 _桥_ 的特殊边感兴趣。连接两个顶点 #cf_span[u] 和 #cf_span[v] 的边被称为 _桥_，当且仅当这条边属...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ q \\in \\mathbb{Z}^+ $ be the number of graphs. \nFor each $ i \\in \\{1, \\dots, q\\} $, let $ n_i \\in \\mathbb{Z}^+ $ be the number of vertices in graph $ i $. \n\n**Constraints** \n...",
"is_translate": false,
"language": "Formal"
}
]
}