На доске написано положительное число \(x\) длины \(n\) в системе счисления с основанием \(p\) (\(2 \le p \le 10^9\)). Число \(x\) задано в виде последовательности \(a_1, a_2, \dots, a_n\) (\(0 \le a_i < p\)) — цифры числа \(x\) в порядке слева направо (от наиболее значащих к наименее).
Дмитрий очень любит все цифры данной системы счисления, поэтому он хочет увидеть каждую из них хотя бы один раз.
За одну операцию он может:
- взять любое число \(x\), написанное на доске, увеличить его на \(1\), и выписать на доску новое значение \(x + 1\).
Например, \(p=5\) и \(x=234_5\).
- Изначально на доске присутствуют цифры \(2\), \(3\) и \(4\);
- Дмитрий увеличивает число \(234_5\) на \(1\) и записывает число \(240_5\). На доске присутствуют цифры \(0, 2, 3, 4\);
- Дмитрий увеличивает число \(240_5\) на \(1\) и записывает число \(241_5\). Теперь на доске присутствуют все цифры от \(0\) до \(4\).
Ваша задача — определить, за какое минимальное количество операций можно получить на доске все цифры от \(0\) до \(p-1\) хотя бы по одному разу.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, за которое Дмитрий сможет получить на доске все цифры от \(0\) до \(p-1\).
Можно показать, что для этого всегда требуется конечное число операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
11
2 3
1 2
4 2
1 1 1 1
6 6
1 2 3 4 5 0
5 2
1 0 1 0 1
3 10
1 2 3
5 1000
4 1 3 2 5
3 5
2 3 4
4 4
3 2 3 0
1 3
2
5 5
1 2 2 2 4
3 4
1 0 1
|
1
1
0
0
7
995
2
1
1
1
2
|