Вам дан массив \(a\) состоящий из \(n\) неотрицательных целых чисел. Гарантируется, что \(a\) отсортирован от меньших к большим.
За одну операцию мы создаем новый массив \(b_i=a_{i+1}-a_{i}\) для всех \(1 \le i < n\). Затем сортируем \(b\) от меньших к большим, заменяем \(a\) на \(b\) и уменьшаем \(n\) на \(1\).
После применения \(n-1\) операции \(n\) становится равным \(1\). Вам нужно вывести единственное целое число в массиве \(a\) (то есть вывести \(a_1\)).
Выходные данные
Для каждого набора входных данных выведите ответ в отдельной строке.
Примечание
Чтобы упростить примечание, обозначим как \(\operatorname{sort}(a)\) массив, получаемый из \(a\) сортировкой от меньших к большим.
В первом наборе изначально \(a=[1,10,100]\). После первой операции \(a=\operatorname{sort}([10-1,100-10])=[9,90]\). После второй операции \(a=\operatorname{sort}([90-9])=[81]\).
Во втором наборе изначально \(a=[4,8,9,13]\). После первой операции \(a=\operatorname{sort}([8-4,9-8,13-9])=[1,4,4]\). После второй операции \(a=\operatorname{sort}([4-1,4-4])=[0,3]\). После последней операции \(a=\operatorname{sort}([3-0])=[3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
1 10 100
4
4 8 9 13
5
0 0 0 8 13
6
2 4 8 16 32 64
7
0 0 0 0 0 0 0
|
81
3
1
2
0
|