King is getting ready for a war. He know his strengths and weeknesses so he is taking required number of soldiers with him. King can only defeat enemies with strongest and weakest power, and one soldier can only kill one enemy. Your task is to calculate that how many soldiers are required by king to take with him for the war.
Note: The array may contain duplicates.
 
Example 1:
Input:
N = 2
A[] = {1, 5}
Output:
0
Explanatation:
The king will itself be able to defeat all the enemies.
 
Example 2:
Input:
N = 3
A[] = {1, 2, 5}
Output:
1
Explanatation:
The king will defeat enemies with power
1 and 5, and he will need 1 soldier to
defeat the enemy with power 2.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function SoldierRequired() which takes the array A[] and its size N as inputs and returns the number of soldiers, king will need to take with him for the war.
Expected Time Complexity: O(NLogN)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ N ≤ 10^{6 }
1 ≤ Ai ≤ 10^{6}
^{Array may contain duplicates}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(NLogN)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
    def SoldierRequired(self, arr, n):
         # Your code goes here 
        


Solutions:
class Solution:

	def SoldierRequired(self, arr, n):
		if n < 2:
			return 0
		d = arr.count(max(arr))
		x = arr.count(min(arr))
		return n - d - x


class Solution:

	def SoldierRequired(self, arr, n):
		arr.sort()
		x = arr[0]
		y = arr[n - 1]
		q = 0
		for i in range(0, n):
			if arr[i] != x and arr[i] != y:
				q = q + 1
		return q


class Solution:

	def SoldierRequired(self, arr, n):
		max1 = max(arr)
		min1 = min(arr)
		b = []
		if n == 2:
			return 0
		else:
			for i in arr:
				if i != max1 and i != min1:
					b.append(i)
			return len(b)


class Solution:

	def SoldierRequired(self, arr, n):
		arr.sort()
		return max(0, n - arr.count(arr[0]) - arr.count(arr[-1]))


class Solution:

	def SoldierRequired(self, arr, n):
		if n > 2:
			n = n - (arr.count(min(arr)) + arr.count(max(arr)))
			return n
		else:
			return 0


class Solution:

	def SoldierRequired(self, arr, n):
		if n > 2:
			arr.sort()
			weak = arr[0]
			strong = arr[n - 1]
			count = 0
			j = n - 1
			while j > -1:
				if arr[j] == strong:
					j -= 1
					count += 1
				else:
					break
			i = 0
			while i < n:
				if arr[i] == weak:
					i += 1
					count += 1
				else:
					break
			return n - count
		return 0


class Solution:

	def SoldierRequired(self, arr, n):
		arr1 = sorted(arr)
		x = arr1.count(max(arr1)) - 1
		y = arr1.count(min(arr1)) - 1
		if n < 2:
			l = 0
		else:
			l = len(arr1) - 2 - x - y
		return l


class Solution:

	def SoldierRequired(self, arr, n):
		if n <= 2:
			return 0
		arr.sort()
		i = 0
		j = n - 1
		while arr[i] == arr[i + 1]:
			i += 1
		while arr[j] == arr[j - 1]:
			j -= 1
		return j - i - 1


class Solution:

	def SoldierRequired(self, arr, n):
		a = max(arr)
		b = min(arr)
		c = 0
		for i in range(0, n):
			if arr[i] != a and arr[i] != b:
				c += 1
		return c


class Solution:

	def SoldierRequired(self, arr, n):
		ma = max(arr)
		mi = min(arr)
		k = n
		for i in range(0, n):
			if arr[i] == ma:
				k -= 1
			if arr[i] == mi:
				k -= 1
		return k if n > 2 else 0


class Solution:

	def SoldierRequired(self, arr, n):
		arr.sort()
		m = arr.count(arr[-1]) - 1
		s = arr.count(arr[0]) - 1
		return len(arr[1:-1]) - s - m


class Solution:

	def SoldierRequired(self, arr, n):
		if n <= 2:
			return 0
		arr.sort()
		return n - arr.count(arr[0]) - arr.count(arr[-1])


class Solution:

	def SoldierRequired(self, arr, n):
		ans = 0
		arr.sort()
		left = 0
		right = n - 1
		if n <= 2:
			return 0
		for i in range(1, n, 1):
			if arr[i - 1] != arr[i]:
				left = i
				break
		for j in range(n - 1, -1, -1):
			if arr[j - 1] != arr[j]:
				right = j - 1
				break
		return right - left + 1


class Solution:

	def SoldierRequired(self, arr, n):
		count = 0
		arr.sort()
		if n <= 2:
			return 0
		if len(set(arr)) == 1:
			return -n
		else:
			for i in range(n):
				if arr[i] > arr[0] and arr[i] < arr[n - 1]:
					count += 1
		return count


class Solution:

	def SoldierRequired(self, arr, n):
		if len(arr) <= 2:
			return 0
		else:
			m = arr.count(max(arr))
			n1 = arr.count(min(arr))
			return n - m - n1


class Solution:

	def SoldierRequired(self, arr, n):
		s = set([min(arr), max(arr)])
		r = []
		for j in arr:
			if j not in s:
				r.append(j)
		return len(r)


class Solution:

	def SoldierRequired(self, a, n):
		count = 0
		a.sort()
		for i in range(n):
			if a[i] == a[0] or a[i] == a[n - 1]:
				continue
			else:
				count += 1
		return count


from collections import Counter

class Solution:

	def SoldierRequired(self, arr, n):
		c = Counter(arr)
		keys = sorted(c)
		del c[keys[0]]
		if c:
			del c[keys[-1]]
		return sum(c.values())


class Solution:

	def SoldierRequired(self, arr, n):
		a = False
		b = False
		ans = 0
		for i in range(n):
			c = arr[i]
			if c < a or a == False:
				a = c
			if c > b or b == False:
				b = c
		for i in range(n):
			if arr[i] != a and arr[i] != b:
				ans += 1
		return ans


class Solution:

	def SoldierRequired(self, arr, n):
		(a, b) = (min(arr), max(arr))
		(x, y) = (arr.count(a), arr.count(b))
		return n - x - y if n - x - y > 0 else 0


class Solution:

	def SoldierRequired(self, arr, n):
		mi = min(arr)
		ma = max(arr)
		co = 0
		for i in arr:
			if i == mi or i == ma:
				co += 1
		return n - co


class Solution:

	def SoldierRequired(self, a, n):
		mn = min(a)
		mx = max(a)
		cmn = 0
		cmx = 0
		for x in a:
			if x == mn:
				cmn += 1
			if x == mx:
				cmx += 1
		return max(0, n - cmn - cmx)


class Solution:

	def SoldierRequired(self, arr, n):
		if n == 1:
			return 0
		arr.sort()
		mi = arr[0]
		ma = arr[n - 1]
		if mi == ma:
			return 0
		return n - arr.count(mi) - arr.count(ma)


class Solution:

	def SoldierRequired(self, arr, n):
		min1 = min(arr)
		b = arr.count(min1)
		max1 = max(arr)
		a = arr.count(max1)
		if n == 1:
			return 0
		if max1 != min1:
			return n - (a + b)
		else:
			return -a


class Solution:

	def SoldierRequired(self, arr, n):
		if n < 3:
			return 0
		(mini, maxi) = (min(arr), max(arr))
		dic = {}
		for i in range(n):
			dic[arr[i]] = dic.get(arr[i], 0) + 1
		ans = 0
		for (k, v) in dic.items():
			if k not in [maxi, mini]:
				ans += v
		return ans


class Solution:

	def SoldierRequired(self, arr, n):
		mini = min(arr)
		maxi = max(arr)
		minicount = arr.count(mini)
		maxicount = arr.count(maxi)
		x = n - (minicount + maxicount)
		return x if x > 0 else 0


class Solution:

	def SoldierRequired(self, arr, n):
		dic = {}
		if n == 1 or n == 2:
			return 0
		for i in arr:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		k = dic[max(arr)] + dic[min(arr)]
		return n - k


class Solution:

	def SoldierRequired(self, arr, n):
		maxi = max(arr)
		mini = min(arr)
		x = arr.count(maxi)
		y = arr.count(mini)
		z = n - x - y
		if z > 0:
			return z
		else:
			return 0


class Solution:

	def SoldierRequired(self, arr, n):
		if n < 3:
			return 0
		else:
			cmn = arr.count(min(arr))
			cmx = arr.count(max(arr))
			return n - cmn - cmx


class Solution:

	def SoldierRequired(self, arr, n):
		arr.sort()
		count = 0
		for i in range(1, n):
			if arr[i] > arr[0] and arr[i] < arr[n - 1]:
				count = count + 1
		return count


class Solution:

	def SoldierRequired(self, arr, n):
		if n > 2:
			a = arr.count(min(arr))
			b = arr.count(max(arr))
			c = n - (a + b)
			return c
		return 0


class Solution:

	def SoldierRequired(self, arr, n):
		if n == 2:
			return 0
		c = arr.count(max(arr))
		d = arr.count(min(arr))
		r = n - c - d
		if r < 1:
			return 0
		return n - c - d


class Solution:

	def SoldierRequired(self, arr, n):
		mx = max(arr)
		mn = min(arr)
		m1 = arr.count(mx)
		m2 = arr.count(mn)
		if n <= 2:
			return 0
		return n - m1 - m2


class Solution:

	def SoldierRequired(self, arr, n):
		mi = min(arr)
		mx = max(arr)
		count = 0
		for i in arr:
			if i == mi or i == mx:
				continue
			else:
				count += 1
		return count


class Solution:

	def SoldierRequired(self, arr, n):
		max1 = max(arr)
		min1 = min(arr)
		count = 0
		for i in range(n):
			if arr[i] == max1 or arr[i] == min1:
				count += 1
		arr.sort()
		if n <= 2:
			return 0
		if n > 2:
			return n - count


class Solution:

	def SoldierRequired(self, arr, n):
		if n == 1 or n == 2:
			return 0
		countmax = 0
		countmin = 0
		mx = max(arr)
		mn = min(arr)
		for i in arr:
			if i == mx:
				countmax += 1
			if i == mn:
				countmin += 1
		return n - countmax - countmin


class Solution:

	def SoldierRequired(self, arr, n):
		p = max(arr)
		q = min(arr)
		count = 0
		for i in arr:
			if i != p and i != q:
				count += 1
		return count


class Solution:

	def SoldierRequired(self, arr, n):
		max1 = max(arr)
		min1 = min(arr)
		(min2, max2) = (0, 0)
		for i in range(n):
			if arr[i] == min1:
				min2 += 1
			elif arr[i] == max1:
				max2 += 1
		return n - max2 - min2


class Solution:

	def SoldierRequired(self, arr, n):
		if len(arr) < 2:
			return 0
		mn = arr.count(min(arr))
		mx = arr.count(max(arr))
		return len(arr) - mx - mn


class Solution:

	def SoldierRequired(self, arr, n):
		if n == 1:
			return 0
		t = arr.count(min(arr))
		t1 = arr.count(max(arr))
		t3 = n - (t + t1)
		return t3


class Solution:

	def SoldierRequired(self, arr, n):
		arr.sort()
		if len(arr) <= 2:
			return 0
		min_count = 1
		for i in range(1, n):
			if arr[i] != arr[i - 1]:
				break
			min_count += 1
		max_count = 1
		for i in range(n - 2, -1, -1):
			if arr[i] != arr[i + 1]:
				break
			max_count += 1
		return n - (min_count + max_count)


class Solution:

	def SoldierRequired(self, arr, n):
		a = max(arr)
		b = min(arr)
		add = 0
		for i in range(n):
			if n < 2:
				return 0
			if arr[i] == a:
				add += 1
			if arr[i] == b:
				add += 1
		diff = n - add
		return diff


class Solution:

	def SoldierRequired(self, arr, n):
		if len(set(arr)) < 3:
			return 0
		else:
			m = min(arr)
			mc = arr.count(m)
			ma = max(arr)
			mac = arr.count(ma)
			sc = n - (mac + mc)
			return sc

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


class Solution:

	def SoldierRequired(self, arr, n):
		if n > 2:
			n = n - (arr.count(min(arr)) + arr.count(max(arr)))
			return n
		else:
			return 0

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


class Solution:

	def SoldierRequired(self, arr, n):
		s = {}
		for i in arr:
			if i in s:
				s[i] += 1
			else:
				s[i] = 1
		m = max(s)
		s[m] = 0
		m = min(s)
		s[m] = 0
		h = 0
		for i in s:
			h += s[i]
		return h

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


class Solution:

	def SoldierRequired(self, arr, n):
		arr.sort()
		l = 0
		r = -1
		while l < n and arr[l] == arr[0]:
			l += 1
		while r >= -1 * n and arr[r] == arr[-1]:
			r -= 1
		r = abs(r) - 1
		return n - (l + r) if n - (l + r) > 0 else 0


class Solution:

	def SoldierRequired(self, arr, n):
		strong = 1
		week = 1
		maxPow = 0
		minPow = 10000000000000001
		for i in range(0, n):
			if arr[i] > maxPow:
				maxPow = arr[i]
				strong = 1
			elif arr[i] == maxPow:
				strong += 1
			if arr[i] < minPow:
				minPow = arr[i]
				week = 1
			elif arr[i] == minPow:
				week += 1
		soldiers = n - (strong + week)
		if soldiers <= 0:
			return 0
		return soldiers


class Solution:

	def SoldierRequired(self, arr, n):
		mx = max(arr)
		mn = min(arr)
		output = []
		for i in range(0, len(arr)):
			if arr[i] == mx or arr[i] == mn:
				continue
			else:
				output.append(arr[i])
		return len(output)


class Solution:

	def SoldierRequired(self, arr, n):
		if n <= 2:
			return 0
		else:
			mini = min(arr)
			maxi = max(arr)
			for i in arr:
				if i == mini or i == maxi:
					n = n - 1
				else:
					pass
			return n


class Solution:

	def SoldierRequired(self, arr, n):
		mi = min(arr)
		ma = max(arr)
		if n <= 1:
			return 0
		return n - arr.count(mi) - arr.count(ma)


class Solution:

	def SoldierRequired(self, arr, n):
		arr.sort()
		strong = arr[-1]
		weak = arr[0]
		ans = 0
		for i in arr:
			if i != strong and i != weak:
				ans += 1
		return ans


class Solution:

	def SoldierRequired(self, arr, n):
		sortedArr = sorted(arr)
		strongest = sortedArr[-1]
		weak = sortedArr[0]
		count = 0
		if n == 2:
			return 0
		else:
			for i in sortedArr:
				if i != strongest and i != weak:
					count += 1
		return count


class Solution:

	def SoldierRequired(self, arr, n):
		d = {}
		for i in arr:
			if i in d.keys():
				d[i] += 1
			else:
				d[i] = 1
		exception = [min(arr), max(arr)]
		soldiers = 0
		for j in d.keys():
			if j not in exception:
				soldiers += d[j]
		return soldiers


class Solution:

	def SoldierRequired(self, arr, n):
		b = arr.count(max(arr))
		s = arr.count(min(arr))
		sol = n - s - b
		if sol >= 0:
			return sol
		else:
			return 0


class Solution:

	def SoldierRequired(self, arr, n):
		arr.sort()
		start_element = arr[0]
		last_index = len(arr) - 1
		last_element = arr[last_index]
		if start_element == last_element:
			return 0
		start_count = arr.count(start_element)
		end_count = arr.count(last_element)
		final_soldiers = len(arr) - start_count - end_count
		return final_soldiers