Решение задачи Квадраты и отрезки с Codeforces

Маленькая София учится в четвертом классе. Сегодня на уроке геометрии она узнала про отрезки и квадраты. По пути домой она решила нарисовать на снегу n квадратов со стороной длины 1. Для простоты будем считать, что София живёт на плоскости и может рисовать только отрезки длины 1, параллельные осям координат, с вершинами в целых точках.

Для того, чтобы нарисовать отрезок, София поступает следующим образом. Пусть она хочет нарисовать вертикальный отрезок с координатами концов (x,y) и (x,y+1). Тогда София смотрит, существует ли уже нарисованный отрезок с координатами концов (x′,y) и (x′,y+1) для какого-нибудь x′. Если такой отрезок существует, то София быстро рисует новый отрезок, используя старый, как ориентир. Если же такого отрезка нет, то Софии приходится брать линейку и долго отмерять новый отрезок. Аналогично София поступает для горизонтальных отрезков, но только теперь она проверяет существование отрезка с такими же координатами x, x+1 и различающейся координатой y.

Например, если Софии надо нарисовать один квадрат, ей придется нарисовать два отрезка с помощью линейки:


После этого можно нарисовать оставшиеся два отрезка, используя первые в качестве ориентира:


Если же Софии надо нарисовать два квадрата, ей придется нарисовать три отрезка с помощью линейки:


После этого можно нарисовать оставшиеся четыре отрезка, используя первые в качестве ориентира:


София торопится домой, поэтому хочет минимизировать число отрезков, которые ей придется рисовать с линейкой без ориентира. Помогите ей найти это минимальное число.