Suppose you are a car driver and you have to drive a car on a track divided into "N" number of sub-tracks. You are also given the value of "K" i.e. the total kilometers the car can drive on each sub-track. If the car can't cover a sub-track, you can add any unit of Petrol to it. With each unit of petrol added, the total kilometers your car can travel will increase by one unit. You have to return the minimum unit of Petrol that if added to your car at each sub-tracks your car will be able to cover all the sub-tracks. If no extra unit of petrol is required, return -1.
 
Example 1:
Input:
N = 5, K = 7
arr[] = {2, 5, 4, 5, 2}
Output:
-1
Explanation:
No extra petrol required, as K is greater
than all the elemnts in the array hence -1.
 
Example 2:
Input:
N = 5, K = 4
arr[] = {1, 6, 3, 5, 2}
Output:
2
Explanation:
You are given 5 sub-tracks with different
kilometers. Your car can travel 4 km on
each sub-track. So, when you come on
sub-track 2nd you have to cover 6 km of
distance, so you need to have 2 unit of
petrol more to cover the distance, for
3rd sub-track, your car can travel 4km 
and you need extra 1 unit of pertrol.So
if you add 2 units of petrol at each sub-track
you can cover all the subtracks.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function required() which takes the array arr[], its size n and an integer k as inputs and returns the minimum unit of Petrol your car requires to cover all the sub-tracks. If no extra unit of petrol is required, return -1.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ K ≤ 10^{18}
1 ≤ A[] ≤ 10^{18}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def required(self, a, n, k):
        # Your code goes here
    


Solutions:
class Solution:

	def required(self, a, n, k):
		g = max(a)
		if g > k:
			return g - k
		return -1


class Solution:

	def required(self, a, n, k):
		max_track = a[0]
		for track in a:
			max_track = max(max_track, track)
		return -1 if max_track <= k else max_track - k


class Solution:

	def required(self, a, n, k):
		a.sort()
		return -1 if a[n - 1] <= k else a[n - 1] - k


class Solution:

	def required(self, a, n, k):
		a.sort()
		curr_petrol = k
		for track in a:
			if track <= curr_petrol:
				continue
			else:
				curr_petrol = track
		return -1 if curr_petrol == k else curr_petrol - k


class Solution:

	def required(self, a, n, k):
		x = max(a)
		if k > x:
			return -1
		elif k == x:
			return -1
		else:
			return x - k


class Solution:

	def required(self, a, n, k):
		add = 0
		for elem in a:
			if elem > k:
				diff = elem - k
				add += diff
				k += diff
		return add if add else -1


class Solution:

	def required(self, a, n, k):
		if k - max(a) < 0:
			return abs(k - max(a))
		else:
			return -1


class Solution:

	def required(self, a, n, k):
		m = max(a)
		if k >= m:
			return -1
		else:
			return m - k


class Solution:

	def required(self, a, n, k):
		c = 0
		if k > max(a) or k == max(a):
			return -1
		else:
			return max(a) - k


class Solution:

	def required(self, a, n, k):
		b = max(a)
		if b > k:
			c = b - k
			return c
		return -1


class Solution:

	def required(self, a, n, k):
		cnt = 0
		l = []
		for i in a:
			if i <= k:
				pass
			else:
				cnt = i - k
				l.append(cnt)
				k = i
		if cnt > 0:
			return sum(l)
		else:
			return -1


class Solution:

	def required(self, a, n, k):
		lis = []
		for i in range(n):
			if a[i] > k:
				lis.append(a[i] - k)
		if len(lis) > 0:
			return max(lis)
		else:
			return -1


class Solution:

	def required(self, a, n, k):
		x = []
		for i in a:
			if k < i:
				x.append(i - k)
		if len(x) == 0:
			return -1
		return max(x)


class Solution:

	def required(self, a, n, k):
		unit = 0
		for i in range(n):
			if a[i] > k:
				unit += a[i] - k
				k = a[i]
		if unit == 0:
			return -1
		return unit


class Solution:

	def required(self, arr, n, k):
		c = -1
		d = max(arr)
		for i in range(n):
			if arr[i] > k:
				c = d - k
		return c


class Solution:

	def required(self, a, n, k):
		res = 0
		for el in a:
			if k - el < 0:
				units = abs(k - el)
				res += units
				k += units
		return res if res != 0 else -1


class Solution:

	def required(self, arr, n, k):
		petrol = 0
		capacity = k
		for i in range(n):
			if arr[i] > capacity:
				petrol += arr[i] - capacity
				capacity += arr[i] - capacity
		if petrol == 0:
			return -1
		return petrol


class Solution:

	def required(self, a, n, k):
		mini = max(a)
		if mini > k:
			return mini - k
		return -1

def main():
	T = int(input())
	while T > 0:
		sz = [int(x) for x in input().strip().split()]
		(n, m) = (sz[0], sz[1])
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.required(a, n, m))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def required(self, a, n, k):
		ans = []
		for i in range(n):
			if a[i] > k:
				ans.append(abs(a[i] - k))
		if ans:
			return max(ans)
		return -1

def main():
	T = int(input())
	while T > 0:
		sz = [int(x) for x in input().strip().split()]
		(n, m) = (sz[0], sz[1])
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.required(a, n, m))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def required(self, a, n, k):
		max_diff = -1
		for i in a:
			if i > k and i - k > max_diff:
				max_diff = i - k
		return max_diff if max_diff > 0 else -1

def main():
	T = int(input())
	while T > 0:
		sz = [int(x) for x in input().strip().split()]
		(n, m) = (sz[0], sz[1])
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.required(a, n, m))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def required(self, a, n, k):
		petrol = 0
		for i in range(n):
			if a[i] > k:
				diff = a[i] - k
				k += diff
				petrol += diff
		if petrol == 0:
			return -1
		return petrol

def main():
	T = int(input())
	while T > 0:
		sz = [int(x) for x in input().strip().split()]
		(n, m) = (sz[0], sz[1])
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.required(a, n, m))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def required(self, a, n, k):
		s = 0
		for i in range(0, n):
			if a[i] - k > s:
				if a[i] > k:
					s = a[i] - k
			i += 1
		if s > 0:
			return s
		else:
			return -1


class Solution:

	def required(self, a, n, k):
		count = 0
		for i in a:
			if i > k:
				count += i - k
				k += i - k
		if count == 0:
			return -1
		return count


class Solution:

	def required(self, a, n, k):
		capacity = k
		for dist in a:
			if capacity < dist:
				capacity += dist - capacity
		return -1 if capacity == k else capacity - k


class Solution:

	def required(self, a, n, k):
		t = k
		for i in a:
			if i - k > 0:
				k += i - k
		return k - t if k - t else -1


class Solution:

	def required(self, a, n, k):
		ans = 0
		f = 1
		for x in a:
			ans = max(ans, x - k)
			if x - k > 0:
				f = 0
		if f:
			return -1
		return ans


class Solution:

	def required(self, a, n, k):
		for i in range(n):
			a[i] = a[i] - k
		maxAmount = 0
		for i in range(n):
			maxAmount = max(maxAmount, a[i])
		if maxAmount == 0:
			return -1
		return maxAmount


import numpy as np

class Solution:

	def required(self, a, n, k):
		if np.max(a) <= k:
			return -1
		else:
			return np.max(a) - k


class Solution:

	def required(self, a, n, k):
		temp = k
		for x in range(n):
			if a[x] > temp:
				temp = a[x]
		if temp == k:
			return -1
		else:
			return temp - k


class Solution:

	def required(self, a, n, k):
		if k >= max(a):
			return -1
		else:
			count = 0
			for i in a:
				if i <= k:
					continue
				else:
					extra = i - k
					count += extra
					k = k + extra
		return count


class Solution:

	def required(self, a, n, k):
		total = 0
		k_ori = k
		for i in range(0, n):
			if a[i] > k:
				total += a[i] - k
				k = a[i]
		if total == 0:
			total = -1
		return total


class Solution:

	def required(self, a, n, k):
		ans = 0
		travel = k
		for i in a:
			if i > travel:
				ans += i - travel
				travel = i
		return ans if ans > 0 else -1


class Solution:

	def required(self, a, n, k):
		if k >= max(a):
			return -1
		maxi = max(a)
		rem = maxi - k
		return rem


import math

class Solution:

	def required(self, a, n, k):
		a.sort()
		b = a[-1]
		if k >= b:
			return -1
		else:
			return abs(b - k)


class Solution:

	def required(self, arr, n, k):
		if max(arr) > k:
			return max(arr) - k
		else:
			return -1


import heapq

class Solution:

	def required(self, a, n, k):
		x = heapq.nlargest(1, a)
		if x[0] - k > 0:
			return x[0] - k
		else:
			return -1


class Solution:

	def required(self, a, n, k):
		cur_km = k
		for km in a:
			cur_km = max(cur_km, km)
		return cur_km - k if cur_km != k else -1


import sys

class Solution:

	def required(self, a, n, k):
		answer = -1
		for num in a:
			if k < num:
				answer = max(answer, abs(num - k))
		return answer