Аллен хочет попасть в фан-зону, которая расположена на круглой площади и имеет \(n\) входов.
Перед \(i\)-м входом уже скопилась очередь из \(a_i\) человек. Каждую минуту каждый вход пропускает ровно один человека в фан-зону.
Аллен использует следующую стратегию для попадания в фан-зону:
- Изначально он стоит в конце очереди к первому входу.
- Каждую минуту, если его не пропустили в фан-зону в течение этой минуты (то есть он был не первым в очереди), он покидает текущую очередь и встает в конец очереди у следующего входа (или первого, если он покинул очередь перед последним входом).
Определите вход, через который Аллен в итоге попадет в фан-зону.
Примечание
В первом примере число людей (не включая Аллена) меняется так: \([\textbf{2}, 3, 2, 0] \to [1, \textbf{2}, 1, 0] \to [0, 1, \textbf{0}, 0]\). Жирным выделена очередь, в которой находится Аллен. Видно, что он войдет в фан-зону через третий вход.
Во втором примере число людей (не включая Аллена) меняется так: \([\textbf{10}, 10] \to [9, \textbf{9}] \to [\textbf{8}, 8] \to [7, \textbf{7}] \to [\textbf{6}, 6] \to \\ [5, \textbf{5}] \to [\textbf{4}, 4] \to [3, \textbf{3}] \to [\textbf{2}, 2] \to [1, \textbf{1}] \to [\textbf{0}, 0]\).
Во втором примере число людей (не включая Аллена) меняется так: \([\textbf{5}, 2, 6, 5, 7, 4] \to [4, \textbf{1}, 5, 4, 6, 3] \to [3, 0, \textbf{4}, 3, 5, 2] \to \\ [2, 0, 3, \textbf{2}, 4, 1] \to [1, 0, 2, 1, \textbf{3}, 0] \to [0, 0, 1, 0, 2, \textbf{0}]\).