Пак Чанек только что купил пустой аквариум и мечтал заполнить его своими любимыми рыбками — рыбой-клоуном. Рыбы-клоуны нравятся Пак Чанеку тем, что они способны менять свой пол по желанию. Поскольку его аквариум очень большой, Пак Чанек хочет купить ровно \(k\) рыб-клоунов, чтобы заполнить его.
Пак Чанек отправляется в местный рыбный магазин. Магазин предоставляет \(n\) рыб-клоунов, пронумерованных от \(1\) до \(n\), причем рыба-клоун \(i\) имеет размер \(a_i\). Изначально каждая рыба-клоун в магазине не имеет определенного пола, но имеет возможность быть отнесенной к двум возможным полам - женскому или мужскому.
В магазине существует процедура, которой должен следовать Пак Чанек, чтобы купить рыбу-клоуна. Владелица магазина будет последовательно показывать на каждую рыбу-клоуна от \(1\) до \(n\) и про каждую рыбу-клоуна спрашивать у Пака Чанека, покупать ее или нет. При этом Пак Чанек должен ответить, прежде чем хозяйка магазина перейдет к следующей рыбе-клоуну. Если Пак Чанек решает купить рыбу-клоуна, о которой его спрашивают, то он также должен немедленно объявить пол, который будет присвоен этой рыбе-клоуну. При назначении пола для спрашиваемой в данный момент рыбы-клоуна должны выполняться следующие условия:
- Если Пак Чанек назначает ее самкой, а до этого он уже покупал рыбу-клоуна женского пола, то размер текущей рыбы должен быть ровно на \(1\) больше, чем размер последней самки.
- Если Пак Чанек считает, что это самец, и он уже покупал самца рыбы-клоуна, то размер этой рыбы должен быть ровно на \(1\) меньше, чем размер последнего самца.
Пак Чанек хочет купить ровно \(k\) рыб-клоунов, таких, что:
- Имеется по крайней мере одна рыба-клоун женского пола и один рыба-клоун мужского пола.
- Среди \(k\) рыб-клоунов, которых покупает Пак Чанек, средний размер самки рыбы-клоуна равен среднему размеру самца рыбы-клоуна.
Пусть \(l\) и \(r\) - соответственно минимальный и максимальный индекс рыбы-клоуна, которую покупает Пак Чанек. Каково минимально возможное значение \(r-l\)?