У Jzzhu в школе учатся n детей. Jzzhu собирается дать им конфет. Пронумеруем всех детей от 1 до n, i-й ребенок хочет получить как минимум ai конфет.
Jzzhu выстроил всех детей в очередь, i-го ребенка он поставил i-м в очереди. Затем Jzzhu начал раздавать конфеты, следуя алгоритму:
- Дать m конфет первому в очереди ребенку.
- Если ребенок получил достаточное количество конфет, то он идет домой, иначе он становится в конец очереди.
- Повторять первые два шага до тех пор, пока в очереди стоит хотя бы один ребенок.
Jzzhu интересно, какой ребенок уйдет домой последним? Найдите номер этого ребенка.
Выходные данные
Выведите единственное целое число — номер ребенка, который уйдет домой последним.
Примечание
Рассмотрим первый пример.
Сперва, ребенок 1 получает 2 конфеты и идет домой. Затем ребенок 2 получает 2 конфеты и идет в конец очереди. Теперь очередь имеет вид: [3, 4, 5, 2] (номера детей в порядке очереди). Затем ребенок номер 3 получает 2 конфеты и идет домой, затем ребенок номер 4 получает 2 конфеты и идет в конец очереди. Теперь очередь имеет вид: [5, 2, 4]. Затем ребенок номер 5 получает 2 конфеты и идет домой. Затем ребенок номер 2 получает две конфеты и идет домой. И наконец, ребенок номер 4 получает 2 конфеты и идет домой.
Ребенок номер 4 идет домой последним.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
1 3 1 4 2
|
4
|
|
2
|
6 4
1 1 2 2 3 3
|
6
|