У Mainak есть массив \(a_1, a_2, \ldots, a_n\) из \(n\) положительных целых чисел. Он сделает следующую операцию с данным массивом ровно один раз:
Mainak хочет максимизировать значение \((a_n - a_1)\) после применения ровно одной такой операции. Определите максимальное значение \((a_n - a_1)\), которое он может получить.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число \(t\) (\(1 \le t \le 50\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число \(n\) (\(1 \le n \le 2000\)) — длину массива.
Вторая строка каждого набора входных данных содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 999\)) — элементы массива.
Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(2000\).
Для каждого набора входных данных выведите единственное целое число — максимальное значение \((a_n - a_1)\), которое Mainak может получить.
5 6 1 3 9 11 5 7 1 20 3 9 99 999 4 2 1 8 1 3 2 1 5
10 0 990 7 4
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач