В конце урока учитель арифметики задал ученикам на дом задание, но Вова очень спешил на перемену и не записал его. Теперь же дома он пытается вспомнить это задание. Он помнит лишь, что это пример, в котором были записаны несколько первых натуральных чисел, перед каждым из них стоял знак сложения или вычитания, и не было скобок:
? 1 ? 2 ? 3 ? ... ? N =
А еще он успел подсмотреть в книгу учителя и знает, что ответом является целое число k. Теперь Вова хочет попытаться восстановить пример из задания.
Во входном файле записано целое число k (|k| ≤ 10^100000.
В выходной файл выведите наименьшее натуральное число N (N ≥ 1), для которого существует хотя бы одна такая расстановка знаков в примере, которая дает ответ k.