Иван разрабатывает свою собственную компьютерную игру. Сейчас Иван хочет создать все уровни игры. Но перед этим он хочет нарисовать каждый уровень на бумаге в виде графа.
Иван решил, что в графе i-го уровня должно быть ровно ni вершин, а сам граф должен быть неориентированный. Главная, по мнению Ивана, характеристика графа — количество специальных рёбер, называемых мостами. Ребро, соединяющее вершины u и v, называется мостом, если оно лежит на каждом пути из u в v (и эти вершины окажутся в разных компонентах связности, если ребро стереть). Иван хочет, чтобы в построенном для каждого уровня графе как минимум 50% всех рёбер были бы мостами. Также Иван хочет максимизировать количество рёбер в каждом графе.
Итак, задание, которое вам дал Иван, состоит в следующем: по заданным q числам n1, n2, ..., nq для каждого i определить максимальное количество рёбер в графе из ni вершин, если хотя бы 50% рёбер должны быть мостами. Обратите внимание, в графах не может быть петель или кратных рёбер.