{"raw_statement":[{"iden":"statement","content":"Для своих научных изысканий Рудольф часто штудирует книги по теории графов и находит в них интересные определения: например, недавно он узнал, что неориентированный граф, у которого все вершины имеют равное количество рёбер-соседей, называют регулярным.\n\nИногда Рудольф вводит собственные термины, если имеющиеся ему чем-то не угодили. Например, ему не понравилось, что понятие регулярности характерно только для неориентированных графов. Кроме того, ограничение, согласно которому из каждой вершины исходит строго одинаковое количество рёбер, показалось ему слишком скучным. Поэтому Рудольф придумал определение квазирегулярного графа.\n\nОриентированный граф является квазирегулярным, если он обладает следующими свойствами:\n\nРудольф остался очень доволен своим новым определением и тут же начал рисовать различные квазирегулярные графы. Спустя некоторое время он обратил внимание на то, что некоторые из нарисованных им графов содержали циклы, тогда как другие — нет. Из книг Рудольф знал, что ациклические графы — это очень здорово, поэтому он принялся подробнее изучать (и рисовать) именно ациклические квазирегулярные графы.\n\nСейчас Рудольф нарисовал на бумаге n точек-вершин. Ему интересно, какое максимальное количество стрелок-рёбер он может дорисовать, чтобы получившийся граф был квазирегулярным и не содержал циклов. Помогите ему найти ответ на этот вопрос.\n\nВвод содержит целое число n (1 ≤ n ≤ 109) — количество вершин графа.\n\nВыведите одно целое число — максимальное количество рёбер ациклического квазирегулярного графа, содержащего n вершин.\n\nИскомый ациклический квазирегулярный граф для первого примера показан на рисунке.\n\n"},{"iden":"входные данные","content":"Ввод содержит целое число n (1 ≤ n ≤ 109) — количество вершин графа."},{"iden":"выходные данные","content":"Выведите одно целое число — максимальное количество рёбер ациклического квазирегулярного графа, содержащего n вершин."},{"iden":"примеры","content":"Входные данные3Выходные данные2Входные данные6Выходные данные12"},{"iden":"примечание","content":"Искомый ациклический квазирегулярный граф для первого примера показан на рисунке.  "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of vertices, with $ 1 \\leq n \\leq 10^9 $.  \nA *quasiregular directed graph* is a directed graph where for every vertex, the out-degree is either $ d $ or $ d+1 $ for some fixed $ d \\in \\mathbb{Z}_{\\geq 0} $, and all in-degrees are equal to some fixed $ k \\in \\mathbb{Z}_{\\geq 0} $.  \n\n**Constraints**  \n1. The graph is acyclic (no directed cycles).  \n2. Each vertex has out-degree $ d $ or $ d+1 $ for some integer $ d \\geq 0 $.  \n3. All vertices have the same in-degree $ k $.  \n\n**Objective**  \nMaximize the total number of edges in such a graph with $ n $ vertices.  \n\n**Solution**  \nIn an acyclic directed graph, vertices can be topologically ordered. To maximize edges under quasiregularity and acyclicity:  \n- All in-degrees must be equal: $ k $.  \n- Out-degrees differ by at most 1.  \n- Maximum edges occur when the graph is a complete DAG with balanced out-degrees.  \n\nThe maximum number of edges in an acyclic directed graph on $ n $ vertices is achieved when the out-degrees are as balanced as possible and in-degrees are uniform.  \n\nThis is achieved by assigning out-degrees:  \n- $ r $ vertices have out-degree $ \\left\\lfloor \\frac{n-1}{2} \\right\\rfloor + 1 $,  \n- $ n - r $ vertices have out-degree $ \\left\\lfloor \\frac{n-1}{2} \\right\\rfloor $,  \n\nbut due to the constraint that *in-degrees are all equal*, and the graph is acyclic, the only way to satisfy both is to have a **complete bipartite DAG** with partitions as equal as possible.  \n\nLet $ a = \\left\\lceil \\frac{n}{2} \\right\\rceil $, $ b = \\left\\lfloor \\frac{n}{2} \\right\\rfloor $.  \nThen maximum edges = $ a \\cdot b $.  \n\nThus:  \n$$\n\\boxed{\\left\\lfloor \\frac{n^2}{4} \\right\\rfloor}\n$$","simple_statement":"Given n vertices, find the maximum number of directed edges you can add to make a cycle-free quasiregular graph.","has_page_source":false}