Не так давно Влад придумал интересную функцию:
- \(f_a(x)=\left\lfloor\frac{x}{a}\right\rfloor + x \bmod a\), где \(\left\lfloor\frac{x}{a}\right\rfloor\) — это \(\frac{x}{a}\), округлённое вниз, \(x \bmod a\) — остаток от целочисленного деления \(x\) на \(a\).
Например при \(a=3\) и \(x=11\), значение \(f_3(11) = \left\lfloor\frac{11}{3}\right\rfloor + 11 \bmod 3 = 3 + 2 = 5\).
Число \(a\) является зафиксированным и известным Владу. Помогите Владу найти максимальное значение \(f_a(x)\), если \(x\) может принять любое целочисленное значение от \(l\) до \(r\) включительно (т.е. \(l \le x \le r\)).
Выходные данные
Для каждого набора входных данных на отдельной строке выведите одно число — максимальное значение функции на данном отрезке при заданном \(a\).
Примечание
В первом примере:
- \(f_3(1) = \left\lfloor\frac{1}{3}\right\rfloor + 1 \bmod 3 = 0 + 1 = 1\),
- \(f_3(2) = \left\lfloor\frac{2}{3}\right\rfloor + 2 \bmod 3 = 0 + 2 = 2\),
- \(f_3(3) = \left\lfloor\frac{3}{3}\right\rfloor + 3 \bmod 3 = 1 + 0 = 1\),
- \(f_3(4) = \left\lfloor\frac{4}{3}\right\rfloor + 4 \bmod 3 = 1 + 1 = 2\)
В качестве ответа, очевидно, подходят \(f_3(2)\) и \(f_3(4)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 4 3
5 8 4
6 10 6
1 1000000000 1000000000
10 12 8
|
2
4
5
999999999
5
|