Дабир, Егор и Арсений только сели в поезд, как они решили сыграть в игру. У Дабира есть рюкзак с бесконечным числом кубиков. Он составил из них $$$n$$$ башен, $$$i$$$-я башня имеет высоту $$$h_i$$$ кубиков.

Егор с Арсением должны для каждой башни $$$i$$$ выбрать число $$$x_i$$$ и увеличить её высоту на $$$x_i$$$ ровно один раз. Например, если $$$h$$$ = [$$$1, 3, 2, 2$$$], $$$x$$$ = [$$$3, 2, 2, 8$$$], то после увеличения $$$h$$$ станет [$$$4, 5, 4, 10$$$]. Их задача сделать высоты всех башен равными.

Чтобы сделать игру интереснее, Дабир хочет выбрать число $$$k$$$ и добавить ограничение: для $$$x_i$$$ должно выполняться $$$1 \le x_i \le k$$$. Помогите ему найти наименьшее $$$k$$$, для которого возможно закончить игру.