Рыбаки поймали много рыб и, конечно, выпили. Наутро пришла пора делить улов. Первый проснувшийся рыбак понял, что для того чтобы поделить рыб поровну, нужно выбросить a₁ рыб. Так он и сделал — выбросил a₁ рыб и забрал свою долю. Второй проснувшийся рыбак не знал о том, что первый рыбак уже взял свою долю. Он поступил так же, как и первый: выбросил a₂ лишних рыб и забрал свою долю. Затем так же поступили и остальные рыбаки.

Зная, сколько рыб выбросил каждый рыбак, найдите минимальное возможное количество рыб, которое могли поймать рыбаки. Известно, что рыбаки поймали хотя бы одну рыбу.

В первой строке записано целое число n (2 ≤ n ≤ 2000). Во второй строке записаны целые числа a₁, …, a_n (0 ≤ a_i ≤ n − 1), где a_i — количество рыб, выброшенных i-м рыбаком.

Выведите минимальное количество рыб, которое должны были поймать рыбаки.