Алекс купил новый роман, изданный в \(n\) томах. Он прочитал все тома друг за другом, потратив на каждый несколько (один или более) полных дней. Другими словами, в первый день он читал первый том, и каждый следующий день он читал либо тоже самый том, что и днем ранее, либо следующий.
Пусть \(v_i\) — это номер тома, который Алекс читал в \(i\)-й день. Ниже представлены некоторые примеры возможных ситуаций:
- вполне возможна ситуация, что \(v_1 = 1\), \(v_2 = 1\), \(v_3 = 2\), \(v_4 = 3\), \(v_5 = 3\). То есть Алекс потратил два дня (\(1\)-й и \(2\)-й) на первый том, один день (\(3\)-й) на второй том и два дня (\(4\)-й и \(5\)-й) на третий том;
- ситуация \(v_1 = 2\), \(v_2 = 2\), \(v_3 = 3\) невозможна, так как Алекс начал чтение с первого тома (таким образом, \(v_1\) не может быть ни чем кроме \(1\));
- ситуация \(v_1 = 1\), \(v_2 = 2\), \(v_3 = 3\), \(v_4 = 1\) невозможна, так как Алекс не вернется к чтению первого тома после чтения третьего;
- ситуация \(v_1 = 1\), \(v_2 = 3\) невозможна, так как Алекс не пропускает тома.
Вы знаете, что Алекс читал том \(v_a\) в день \(a\) и том \(v_c\) в день \(c\). Теперь вы хотите угадать, какой том он читал в день \(b\), что находится между днями \(a\) и \(c\) (то есть, \(a < b < c\)). Возможно, однозначного ответа нет, а потому вас устроит любой подходящий по номеру том (т. е. выберете такое значение \(v_b\), что возможна ситуация, когда Алекс читал том \(v_a\) в день \(a\), том \(v_b\) в день \(b\) и том \(v_c\) в день \(c\)).
Выходные данные
Для каждого набора входных данных, выведите номер тома, который Алекс мог читать в день \(b\). Если существует несколько ответов, выведите любой из них.
Примечание
В первом наборе входных данных, так как Алекс читал том \(1\) как в день \(1\) так и в день \(100\), то он совершенно точно читал том \(1\) в любой другой день между ними.
Во втором наборе, Алекс мог читать любой том от \(1\) по \(4\) в день \(16\). Например, он мог читать том \(1\) со дня \(1\) по день \(15\), том \(2\) в дни \(16\) и \(17\), том \(3\) в день \(18\) и том \(4\) в дни \(19\) и \(20\).
В третьем наборе входных данных, возможна только одна ситуация: Алекс читал по тому в день, а потому в день \(42\) он читал том \(42\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
1 1
100 1
99
4
10 1
20 4
16
100
1 1
100 100
42
100
1 1
100 2
99
|
1
2
42
1
|