Ishwar has got proposals from N girls. Each girl gives him a rose with a number written on it where the number represents the popularity of that girl. Ishwar decides that he'll accept the proposal of the second most popular and the second least popular girl only. Can you help him finding the popularity of those girls?
Note: The popularity of all the girls are unique.
Example 1:
Input:
N = 4
arr[] = {1 2 3 4}
Output: 3 2
Explanation: 3 represents the popularity
of the second most popular girl and 2
represents the popularity of second
least popular girl.
Example 2:
Input:
N = 5
arr[] = {6 9 1 4 8}
Output: 8 4
Explanation: 8 represents the popularity
of the second most popular girl and 4
represents the popularity of second
least popular girl.
Your Task:
You don't need to read input or print anything. Your task is to complete the function acceptedProposals() which takes the array arr[] and its size N as inputs and returns an array of size 2 where the 0-th element represents the popularity of the second most popular girl and the 1-st element represents the popularity of the second least popular girl.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraint:
2 <= N <= 10^{5}
1 <= popularity <= 10^{6}

Difficulty: EASY
Tags: Sorting
Skill types: Sorting
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3

class Solution:
    def acceptedProposals (self,arr, n):
        # your code here

Solutions:
class Solution:

	def acceptedProposals(self, arr, n):
		arr.sort()
		return (arr[n - 2], arr[1])


class Solution:

	def acceptedProposals(self, arr, n):
		arr.sort()
		b = []
		b.append(arr[-2])
		b.append(arr[1])
		return b


class Solution:

	def acceptedProposals(self, arr, n):
		arr.sort()
		c = []
		c.append(arr[1])
		c.append(arr[n - 2])
		d = []
		d = c[-1::-1]
		return d


class Solution:

	def acceptedProposals(self, arr, n):
		k = sorted(arr)
		return (k[-2], k[1])


class Solution:

	def acceptedProposals(self, arr, n):
		a = sorted(arr)
		return (a[-2], a[1])


class Solution:

	def acceptedProposals(self, arr, n):
		res = []
		arr.remove(max(arr))
		res.append(max(arr))
		arr.remove(min(arr))
		res.append(min(arr))
		return res


class Solution:

	def acceptedProposals(self, arr, n):
		arr.sort()
		b = arr[::-1]
		return (b[1], arr[1])


class Solution:

	def acceptedProposals(self, arr, n):
		arr.sort()
		if n == 2:
			return arr[::-1]
		else:
			return [arr[n - 2], arr[1]]


class Solution:

	def acceptedProposals(self, arr, n):
		(sec_max, sec_min) = (0, 0)
		(max1, min1) = (-100000, 100000)
		for i in range(n):
			if arr[i] < min1:
				sec_min = min1
				min1 = arr[i]
			elif arr[i] < sec_min:
				sec_min = arr[i]
		for i in range(n):
			if arr[i] > max1:
				sec_max = max1
				max1 = arr[i]
			elif arr[i] > sec_max:
				sec_max = arr[i]
		return [sec_max, sec_min]


class Solution:

	def acceptedProposals(self, arr, n):
		lea1 = lea2 = 100000000.0
		gre1 = gre2 = 0
		for i in range(n):
			if arr[i] < lea1:
				lea2 = lea1
				lea1 = arr[i]
			elif arr[i] < lea2:
				lea2 = arr[i]
			if arr[i] > gre1:
				gre2 = gre1
				gre1 = arr[i]
			elif arr[i] > gre2:
				gre2 = arr[i]
		return (gre2, lea2)


class Solution:

	def acceptedProposals(self, arr, n):
		mini = min(arr)
		maxi = max(arr)
		for i in arr:
			if i != mini and i > mini and (i < maxi):
				maxi = i
		m1 = maxi
		mini = min(arr)
		maxi = max(arr)
		for i in arr:
			if i != maxi and i < maxi and (i > mini):
				mini = i
		m2 = mini
		return (m2, m1)


class Solution:

	def acceptedProposals(self, arr, n):
		arr.remove(max(arr))
		arr.remove(min(arr))
		return (max(arr), min(arr))


class Solution:

	def acceptedProposals(self, arr, n):
		maxi = float('-inf')
		secmaxi = float('-inf')
		mini = float('inf')
		secmini = float('inf')
		for i in arr:
			if i > maxi:
				secmaxi = maxi
				maxi = i
			if i < maxi and i > secmaxi:
				secmaxi = i
			if i < mini:
				secmini = mini
				mini = i
			if i > mini and i < secmini:
				secmini = i
		return [secmaxi, secmini]


def secondLargest(arr, n):
	largest = -999999999
	second = -999999999
	for i in range(0, n):
		largest = max(largest, arr[i])
	for i in range(0, n):
		if arr[i] != largest:
			second = max(second, arr[i])
	return second

def secondSmallest(arr, n):
	mini = 999999999
	second_mini = 999999999
	for i in range(0, n):
		mini = min(mini, arr[i])
	for i in range(0, n):
		if arr[i] != mini:
			second_mini = min(second_mini, arr[i])
	return second_mini

class Solution:

	def acceptedProposals(self, arr, n):
		ans1 = secondLargest(arr, n)
		ans2 = secondSmallest(arr, n)
		return [ans1, ans2]
t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ob = Solution()
	res = ob.acceptedProposals(arr, n)
	print(res[0], end=' ')
	print(res[1])


class Solution:

	def acceptedProposals(self, arr, n):
		arr.sort()
		return [arr[n - 2], arr[1]]
t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ob = Solution()
	res = ob.acceptedProposals(arr, n)
	print(res[0], end=' ')
	print(res[1])


class Solution:

	def acceptedProposals(self, arr, n):
		temp = []
		b = sorted(arr)
		temp.append(b[len(b) - 2])
		temp.append(b[1])
		return temp
t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ob = Solution()
	res = ob.acceptedProposals(arr, n)
	print(res[0], end=' ')
	print(res[1])


class Solution:

	def acceptedProposals(self, arr, n):
		max1 = -1
		max2 = -2
		min1 = 99999
		min2 = 99999
		for i in arr:
			if i > max1:
				max2 = max1
				max1 = i
			elif i > max2 and i < max1:
				max2 = i
			if i < min1:
				min2 = min1
				min1 = i
			elif min1 < i and min2 > i:
				min2 = i
		a = []
		a.append(max2)
		a.append(min2)
		return a
t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ob = Solution()
	res = ob.acceptedProposals(arr, n)
	print(res[0], end=' ')
	print(res[1])


import sys

class Solution:

	def acceptedProposals(self, arr, n):
		l = []
		m1 = max(arr)
		m2 = -sys.maxsize
		for i in range(n):
			if arr[i] >= m2 and arr[i] < m1:
				m2 = arr[i]
		m3 = min(arr)
		m4 = sys.maxsize
		for i in range(n):
			if arr[i] > m3 and arr[i] < m4:
				m4 = arr[i]
		l.append(m2)
		l.append(m4)
		return l
t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ob = Solution()
	res = ob.acceptedProposals(arr, n)
	print(res[0], end=' ')
	print(res[1])


class Solution:

	def acceptedProposals(self, arr, n):
		arr.sort()
		a = []
		for i in range(n):
			a.append(arr[-2])
			a.append(arr[1])
		return a


class Solution:

	def acceptedProposals(self, arr, n):
		mx = max(arr)
		mi = min(arr)
		arr.remove(mx)
		arr.remove(mi)
		mx1 = max(arr)
		mi1 = min(arr)
		return (mx1, mi1)
t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ob = Solution()
	res = ob.acceptedProposals(arr, n)
	print(res[0], end=' ')
	print(res[1])


class Solution:

	def acceptedProposals(self, arr, n):
		(max_1, max_2, min_1, min_2) = (-1, -1, 10 ** 6, 10 ** 6)
		for i in arr:
			if i > max_1:
				max_2 = max_1
				max_1 = i
			elif i > max_2:
				max_2 = i
			if i < min_1:
				min_2 = min_1
				min_1 = i
			elif i < min_2:
				min_2 = i
		return (max_2, min_2)


class Solution:

	def acceptedProposals(self, arr, n):
		arr.sort(reverse=True)
		return [arr[1], arr[n - 2]]


class Solution:

	def acceptedProposals(self, arr, n):
		res = []
		if n == 2:
			res.append(min(arr))
			res.append(max(arr))
		else:
			arr.remove(max(arr))
			arr.remove(min(arr))
			res.append(max(arr))
			res.append(min(arr))
		return res


class Solution:

	def acceptedProposals(self, arr, n):
		arr = list(set(arr))
		if len(arr) == 1:
			return -1
		arr.sort()
		return (arr[len(arr) - 2], arr[1])