Given 2 sorted arrays Ar1 and Ar2 of size N each. Merge the given arrays and find the sum of the two middle elements of the merged array.
 
Example 1:
Input:
N = 5
Ar1[] = {1, 2, 4, 6, 10}
Ar2[] = {4, 5, 6, 9, 12}
Output: 11
Explanation: The merged array looks like
{1,2,4,4,5,6,6,9,10,12}. Sum of middle
elements is 11 (5 + 6).
 
Example 2:
Input:
N = 5
Ar1[] = {1, 12, 15, 26, 38}
Ar2[] = {2, 13, 17, 30, 45}
Output: 32
Explanation: The merged array looks like
{1, 2, 12, 13, 15, 17, 26, 30, 38, 45} 
sum of middle elements is 32 (15 + 17).
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function findMidSum() which takes  ar1, ar2 and n as input parameters and returns the sum of middle elements. 
 
Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{3}
1 <= Ar1[i] <= 10^{6}
1 <= Ar2[i] <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Divide and conquer

Starter code: #User function Template for python3



class Solution:

	def findMidSum(self, ar1, ar2, n): 

		# code here 

Solutions:
class Solution:

	def findMidSum(self, ar1, ar2, n):
		ar1.extend(ar2)
		ar3 = sorted(ar1)
		ind = int(len(ar3) / 2)
		summ = ar3[ind - 1] + ar3[ind]
		return summ


class Solution:

	def findMidSum(self, ar1, ar2, n):
		arr = ar1 + ar2
		arr.sort()
		length = len(arr)
		return arr[length // 2] + arr[length // 2 - 1]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		ar1.extend(ar2)
		ar1.sort()
		l = len(ar1)
		return ar1[l // 2 - 1] + ar1[l // 2]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		ar1 += ar2
		ar1.sort()
		return ar1[n - 1] + ar1[n]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		arr = sorted(ar1 + ar2)
		n1 = len(arr)
		start = 0
		end = n1 - 1
		while start <= end:
			start += 1
			end -= 1
		n1 = arr[start - 1] + arr[end + 1]
		return n1


class Solution:

	def findMidSum(self, ar1, ar2, n):
		l = []
		(i, j) = (0, 0)
		while i < n and j < n:
			if ar1[i] < ar2[j]:
				l.append(ar1[i])
				i += 1
			elif ar1[i] > ar2[j]:
				l.append(ar2[j])
				j += 1
			else:
				l.append(ar1[i])
				l.append(ar2[j])
				i += 1
				j += 1
		if i < n:
			l.append(ar1[i])
			i += 1
		if j < n:
			l.append(ar2[j])
			j += 1
		sum = l[n - 1] + l[n]
		return sum


class Solution:

	def findMidSum(self, ar1, ar2, n):
		arr = []
		(i, j) = (0, 0)
		while i < n and j < n:
			if ar1[i] <= ar2[j]:
				arr.append(ar1[i])
				i += 1
			else:
				arr.append(ar2[j])
				j += 1
		while i < n:
			arr.append(ar1[i])
			i += 1
		while j < n:
			arr.append(ar2[j])
			j += 1
		mid = n - 1
		return arr[mid] + arr[mid + 1]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		arr = sorted(ar1 + ar2)
		return arr[n] + arr[n - 1]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		ar1.extend(ar2)
		ar1.sort()
		mid = len(ar1) // 2
		a = ar1[mid] + ar1[mid - 1]
		return a


class Solution:

	def findMidSum(self, ar1, ar2, n):
		arr = [0] * (n + n)
		i = j = k = 0
		while i < n and j < n:
			if ar1[i] <= ar2[j]:
				arr[k] = ar1[i]
				i += 1
			else:
				arr[k] = ar2[j]
				j += 1
			k += 1
		while i < n:
			arr[k] = ar1[i]
			i += 1
			k += 1
		while j < n:
			arr[k] = ar2[j]
			j += 1
			k += 1
		s = 0
		e = n + n - 1
		mid = s + (e - s) // 2
		sum = arr[mid] + arr[mid + 1]
		return sum


class Solution:

	def findMidSum(self, ar1, ar2, n):
		list1 = []
		for i in ar1:
			list1.append(i)
		for i in ar2:
			list1.append(i)
		list1.sort()
		leg = len(list1) // 2 - 1
		sum = list1[leg] + list1[leg + 1]
		return sum


class Solution:

	def findMidSum(self, ar1, ar2, n):
		a = []
		p = 0
		q = 0
		for i in range(n + 1):
			if p == n:
				for j in range(q, n):
					a.append(ar2[j])
				return a[n - 1] + a[n]
			if q == n:
				for j in range(p, n):
					a.append(ar1[j])
				return a[n - 1] + a[n]
			if ar1[p] < ar2[q]:
				a.append(ar1[p])
				p += 1
			else:
				a.append(ar2[q])
				q += 1
		return a[-1] + a[-2]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		arr = [0] * (n * 2)
		(i, j, k) = (0, 0, 0)
		while i < n and j < n:
			if ar1[i] < ar2[j]:
				arr[k] = ar1[i]
				i += 1
			else:
				arr[k] = ar2[j]
				j += 1
			k += 1
		while i < n:
			arr[k] = ar1[i]
			k += 1
			i += 1
		while j < n:
			arr[k] = ar2[j]
			k += 1
			j += 1
		return arr[n - 1] + arr[n]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		if n == 1:
			return ar1[0] + ar2[0]
		count = 0
		(l1, l2) = (0, 0)
		prev_value = 0
		latest_value = 0
		while count != n + 1 and l1 < n and (l2 < n):
			if ar1[l1] < ar2[l2]:
				prev_value = latest_value
				latest_value = ar1[l1]
				l1 += 1
			else:
				prev_value = latest_value
				latest_value = ar2[l2]
				l2 += 1
			count += 1
		if l1 == n:
			for i in range(count, n + 1):
				prev_value = latest_value
				latest_value = ar2[l2]
				l2 += 1
		if l2 == n:
			for i in range(count, n + 1):
				prev_value = latest_value
				latest_value = ar1[l1]
				l1 += 1
		return latest_value + prev_value


class Solution:

	def findMidSum(self, ar1, ar2, n):
		a = ar1 + ar2
		a.sort()
		k = len(a) // 2
		return a[k - 1] + a[k]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		s = 0
		ar1 = ar1 + ar2
		ar1 = sorted(ar1)
		k = len(ar1)
		a = k // 2 - 1
		b = k // 2
		if k % 2 == 0:
			s = s + ar1[a]
			s = s + ar1[b]
		else:
			s = s + ar1[a]
		return s


class Solution:

	def findMidSum(self, a1, a2, n):
		res = 0
		l1 = 0
		l2 = 0
		for i in range(n + 1):
			if l1 == n or (l2 < n and a1[l1] > a2[l2]):
				if i == n - 1 or i == n:
					res += a2[l2]
				l2 += 1
			else:
				if i == n - 1 or i == n:
					res += a1[l1]
				l1 += 1
		return res


class Solution:

	def findMidSum(self, ar1, ar2, n):
		ar1.extend(ar2)
		ar1.sort()
		length = len(ar1)
		mid = length // 2
		sm = ar1[mid - 1] + ar1[mid]
		return sm


class Solution:

	def findMidSum(self, ar1, ar2, n):
		arr3 = sorted(ar1 + ar2)
		return arr3[n - 1] + arr3[n]


class Solution:

	def findMidSum(self, a, b, n):
		i = 0
		j = 0
		k = n
		while 1:
			if k == 1:
				if a[i] < b[j]:
					x = a[i]
					i += 1
				else:
					x = b[j]
					j += 1
				if i >= n:
					y = b[j]
				elif j >= n:
					y = a[i]
				elif a[i] < b[j]:
					y = a[i]
					i += 1
				else:
					y = b[j]
					j += 1
				break
			if a[i] < b[j]:
				i += 1
				k -= 1
			else:
				j += 1
				k -= 1
		return x + y


class Solution:

	def findMidSum(self, ar1, ar2, n):
		v = 0
		i = 0
		ar3 = [0] * 2 * n
		while n != 0:
			if i % 2 == 0:
				ar3[i] = ar1[v]
			else:
				ar3[i] = ar2[v]
				v += 1
				n -= 1
			i += 1
		ar3.sort()
		i = int(len(ar3) / 2)
		return ar3[i] + ar3[i - 1]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		c = []
		c.extend(ar1)
		c.extend(ar2)
		c.sort()
		N = len(c)
		return c[N // 2] + c[N // 2 - 1]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		l = []
		k = min(len(ar1), len(ar2))
		j = 0
		i = 0
		for k in range(len(ar1) + len(ar2)):
			if i <= len(ar1) and j <= len(ar2):
				if j == n or (i < len(ar1) and ar1[i] <= ar2[j]):
					l.append(ar1[i])
					i = i + 1
				else:
					l.append(ar2[j])
					j = j + 1
		sum = l[len(l) // 2 - 1] + l[len(l) // 2]
		return sum


class Solution:

	def findMidSum(self, ar1, ar2, n):
		merged_list = ar1 + ar2
		merged_list = sorted(merged_list)
		merge_length = len(merged_list)
		if merge_length == 0:
			return -1
		else:
			sum = merged_list[n - 1] + merged_list[n]
			return sum


class Solution:

	def findMidSum(self, ar1, ar2, n):
		for i in ar1:
			ar2.append(i)
		ar2.sort()
		return ar2[n] + ar2[n - 1]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		merged = sorted(ar1 + ar2)
		return merged[n - 1] + merged[n]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		arr3 = ar1 + ar2
		arr3.sort()
		n1 = len(arr3)
		val1 = n1 // 2
		summ = arr3[val1 - 1] + arr3[val1]
		return summ


class Solution:

	def findMidSum(self, ar1, ar2, n):
		i = j = 0
		curr = 0
		k = -1
		res = 0
		while i < n and j < n:
			if ar1[i] < ar2[j]:
				curr = ar1[i]
				i += 1
			else:
				curr = ar2[j]
				j += 1
			k += 1
			if k == n - 1:
				res += curr
			if k == n:
				res += curr
				break
			if i == n:
				res += ar2[j]
				break
			if j == n:
				res += ar1[i]
				break
		return res


class Solution:

	def findMidSum(self, ar1, ar2, n):
		ans = []
		for i in range(n):
			ans.append(ar1[i])
			ans.append(ar2[i])
		ans.sort()
		return ans[2 * n // 2 - 1] + ans[2 * n // 2]


import numpy as np

class Solution:

	def findMidSum(self, ar1, ar2, n):
		ar1 = np.array(ar1)
		ar2 = np.array(ar2)
		arr = np.concatenate((ar1, ar2))
		arr.sort()
		mid = len(arr) // 2
		a = arr[mid] + arr[mid - 1]
		return a


class Solution:

	def findMidSum(self, ar1, ar2, n):
		b = ar1 + ar2
		b.sort()
		d = 2 * n // 2
		d1 = 2 * n // 2 + 1
		return b[d - 1] + b[d1 - 1]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		if n == 0:
			return -1
		elif n == 1:
			return ar1[0] + ar2[0]
		elif n == 2:
			return max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])
		else:
			m1 = self.getMidSum(ar1, n)
			m2 = self.getMidSum(ar2, n)
			if m1 > m2:
				if n % 2 == 0:
					return self.findMidSum(ar1[:int(n / 2) + 1], ar2[int(n / 2) - 1:], int(n / 2) + 1)
				else:
					return self.findMidSum(ar1[:int(n / 2) + 1], ar2[int(n / 2):], int(n / 2) + 1)
			elif n % 2 == 0:
				return self.findMidSum(ar1[int(n / 2 - 1):], ar2[:int(n / 2 + 1)], int(n / 2) + 1)
			else:
				return self.findMidSum(ar1[int(n / 2):], ar2[0:int(n / 2) + 1], int(n / 2) + 1)

	def getMidSum(self, arr, n):
		if n % 2 == 0:
			return arr[int(n / 2)] + arr[int(n / 2) - 1]
		else:
			return 2 * arr[int(n / 2)]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		Ar = ar1 + ar2
		Ar.sort()
		l1 = len(Ar)
		val = l1 // 2
		sum = Ar[val - 1] + Ar[val]
		return sum


class Solution:

	def findMidSum(self, ar1, ar2, n):
		i = n - 1
		j = 0
		while i > -1 and j < n and (ar1[i] > ar2[j]):
			(ar1[i], ar2[j]) = (ar2[j], ar1[i])
			i -= 1
			j += 1
		return max(ar1) + min(ar2)


class Solution:

	def findMidSum(self, ar1, ar2, n):
		arr = ar1 + ar2
		x = sorted(arr)
		y = len(x)
		z = y // 2
		summ = x[z - 1] + x[z]
		return summ


class Solution:

	def findMidSum(self, ar1, ar2, n):
		result = ar1 + ar2
		result = sorted(result)
		y = 0
		if len(result) % 2 == 0:
			x = len(result) // 2
			y += sum(result[x - 1:x + 1])
		else:
			x = len // 2
			y += sum(result[x:x + 1])
		return y


class Solution:

	def findMidSum(self, ar1, ar2, n):
		n = ar1 + ar2
		n.sort()
		le = len(n)
		a = le // 2
		b = le // 2 + 1
		sum1 = n[a - 1] + n[b - 1]
		return sum1


class Solution:

	def findMidSum(self, ar1, ar2, n):
		l1 = []
		l1 = ar1 + ar2
		l1.sort()
		b = len(l1)
		mid = b // 2
		c = l1[mid] + l1[mid - 1]
		return c


class Solution:

	def findMidSum(self, arr1, arr2, n):
		(i, j) = (0, 0)
		k = n - 1
		while i <= k and j < n:
			if arr1[i] < arr2[j]:
				i += 1
			else:
				(arr1[k], arr2[j]) = (arr2[j], arr1[k])
				j += 1
				k -= 1
		arr1.sort()
		arr2.sort()
		arr = list(arr1) + list(arr2)
		mid = len(arr) // 2
		s = arr[mid] + arr[mid - 1]
		return s


class Solution:

	def findMidSum(self, ar1, ar2, n):
		a = []
		for i in range(n):
			a.append(ar1[i])
		j = 0
		for i in range(n, n + n):
			a.append(ar2[j])
			j += 1
		a.sort()
		return a[n - 1] + a[n]


class Solution:

	def findMidSum(self, A, B, n):
		i = 0
		j = 0
		p = 0
		ans = [0] * (n + n)
		while i < n and j < n:
			if A[i] <= B[j]:
				ans[p] = A[i]
				i += 1
			else:
				ans[p] = B[j]
				j += 1
			p += 1
		while i < n:
			ans[p] = A[i]
			p += 1
			i += 1
		while j < n:
			ans[p] = B[j]
			p += 1
			j += 1
		return ans[n] + ans[n - 1]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		ar3 = sorted(ar1 + ar2)
		middle_element = len(ar3) // 2
		return ar3[middle_element] + ar3[middle_element - 1]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		lst = []
		lst.extend(ar1)
		lst.extend(ar2)
		lst.sort()
		if len(lst) % 2 == 0:
			return lst[int(n * 2 / 2)] + lst[int(n * 2 / 2 - 1)]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		a = ar1 + ar2
		a.sort()
		return sum(a[n - 1:n + 1])


class Solution:

	def findMidSum(self, ar1, ar2, n):
		arr = ar1 + ar2
		arr.sort()
		l = len(arr)
		sum = 0
		mid = l // 2
		sum = arr[mid] + arr[mid - 1]
		return sum


class Solution:

	def findMidSum(self, ar1, ar2, n):
		(prev, t) = (0, 0)
		(i, j, c) = (0, 0, 0)
		while i < n and j < n:
			if ar1[i] < ar2[j]:
				prev = ar1[i]
				i += 1
			else:
				prev = ar2[j]
				j += 1
			c += 1
			if c == n or c == n + 1:
				t += prev
		if i < n and c == n:
			t += ar1[i]
		if j < n and c == n:
			t += ar2[j]
		return t


class Solution:

	def findMidSum(self, ar1, ar2, n):
		if n == 1:
			return ar1[0] + ar2[0]
		low = 0
		high = n - 1
		while low <= high:
			mid1 = low + (high - low) // 2
			mid2 = n - mid1
			left1 = -10 ** 9 if mid1 == 0 else ar1[mid1 - 1]
			left2 = -10 ** 9 if mid2 == 0 else ar2[mid2 - 1]
			right1 = 10 ** 9 if mid1 == n else ar1[mid1]
			right2 = 10 ** 9 if mid2 == n else ar2[mid2]
			if left1 <= right2 and left2 <= right1:
				return max(left1, left2) + min(right1, right2)
			elif left1 > right2:
				high = mid1 - 1
			else:
				low = mid1 + 1


class Solution:

	def findMidSum(self, ar1, ar2, n):
		final = []
		final.extend(ar1)
		final.extend(ar2)
		final = sorted(final)
		middle = len(final) // 2
		return final[middle - 1] + final[middle]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		ar3 = ar1 + ar2
		ar3.sort()
		mid = len(ar3) // 2
		sum = ar3[mid] + ar3[mid - 1]
		return sum


class Solution:

	def findMidSum(self, ar1, ar2, n):
		ar1.extend(ar2)
		ar1.sort()
		s = ar1[2 * n // 2] + ar1[2 * n // 2 - 1]
		return s


class Solution:

	def findMidSum(self, ar1, ar2, n):
		arr = ar1 + ar2
		arr.sort()
		mid = n - 1
		return arr[mid] + arr[mid + 1]


from typing import List

class Solution:

	def findMidSum(self, ar1: List[int], ar2: List[int], n: int) -> int:
		i = 0
		j = 0
		merged = []
		while i < n and j < n:
			if ar1[i] < ar2[j]:
				merged.append(ar1[i])
				i += 1
			else:
				merged.append(ar2[j])
				j += 1
		while i < n:
			merged.append(ar1[i])
			i += 1
		while j < n:
			merged.append(ar2[j])
			j += 1
		mid = n - 1
		return merged[mid] + merged[mid + 1]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		merged = []
		i = j = 0
		while i < n and j < n:
			if ar1[i] < ar2[j]:
				merged.append(ar1[i])
				i += 1
			else:
				merged.append(ar2[j])
				j += 1
		while i < n:
			merged.append(ar1[i])
			i += 1
		while j < n:
			merged.append(ar2[j])
			j += 1
		if len(merged) % 2 == 1:
			return 2 * merged[len(merged) // 2]
		else:
			return merged[len(merged) // 2 - 1] + merged[len(merged) // 2]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		temp = ar1 + ar2
		temp.sort()
		mid = len(temp) // 2
		ans = temp[mid - 1] + temp[mid]
		return ans


class Solution:

	def findMidSum(self, ar1, ar2, n):
		i = 0
		j = 0
		res = []
		while i < n and j < n:
			if ar1[i] < ar2[j]:
				res.append(ar1[i])
				i += 1
			elif ar2[j] < ar1[i]:
				res.append(ar2[j])
				j += 1
			else:
				res.append(ar1[i])
				res.append(ar2[j])
				i += 1
				j += 1
		if i < n:
			for k in range(i, n):
				res.append(ar1[k])
		else:
			for k in range(j, n):
				res.append(ar2[k])
		n1 = len(res)
		mid = int(n1 / 2)
		return res[mid - 1] + res[mid]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		arr = ar1 + ar2
		arr.sort()
		high = len(arr) - 1
		low = 0
		mid = (high + low) // 2
		return arr[mid] + arr[mid + 1]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		arr3 = ar1 + ar2
		arr3.sort()
		val = len(arr3) // 2
		sum1 = arr3[val - 1] + arr3[val]
		return sum1


class Solution:

	def findMidSum(self, ar1, ar2, n):
		l = []
		for i in ar1:
			l.append(i)
		for i in ar2:
			l.append(i)
		l.sort()
		mid = len(l) // 2
		return l[mid - 1] + l[mid]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		ar3 = ar1 + ar2
		s = sorted(ar3)
		mid = len(s) // 2
		return s[mid] + s[mid - 1]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		ar1.sort()
		ar2.sort()
		d = n * 2
		y = []
		y = ar1 + ar2
		y.sort()
		i = d // 2
		sum = 0
		sum = y[i - 1] + y[i]
		return sum


class Solution:

	def findMidSum(self, array1, array2, n):
		start = 0
		end = n
		real_mid = n
		while start <= end:
			cut1 = (start + end) // 2
			cut2 = real_mid - cut1
			left1 = array1[cut1 - 1] if cut1 > 0 else float('-inf')
			left2 = array2[cut2 - 1] if cut2 > 0 else float('-inf')
			right1 = array1[cut1] if cut1 < n else float('inf')
			right2 = array2[cut2] if cut2 < n else float('inf')
			if left1 <= right2 and left2 <= right1:
				sum_median = max(left1, left2) + min(right1, right2)
				return sum_median
			elif left1 > right2:
				end = cut1 - 1
			else:
				start = cut1 + 1


class Solution:

	def get_count(self, ar1, ar2, mid, n):
		count = 0
		count += len([i for i in ar1 if i <= mid])
		count += len([i for i in ar2 if i <= mid])
		return count

	def findMidSum(self, array1, array2, n):
		start = 0
		end = n
		real_mid = (n + n + 1) // 2
		while start <= end:
			cut1 = (start + end) // 2
			cut2 = real_mid - cut1
			left1 = array1[cut1 - 1] if cut1 > 0 else float('-inf')
			left2 = array2[cut2 - 1] if cut2 > 0 else float('-inf')
			right1 = array1[cut1] if cut1 < n else float('inf')
			right2 = array2[cut2] if cut2 < n else float('inf')
			if left1 <= right2 and left2 <= right1:
				sum_median = max(left1, left2) + min(right1, right2)
				return sum_median
			elif left1 > right2:
				end = cut1 - 1
			else:
				start = cut1 + 1


class Solution:

	def findMidSum(self, ar1, ar2, n):
		s = ar1 + ar2
		r = sorted(s)
		return r[n] + r[n - 1]


class Solution:

	def findMidSum(self, ar1, ar2, n):
		(first, second) = (None, None)
		(i, j) = (0, 0)
		counter = 0
		while i < n and j < n:
			counter += 1
			if counter == n:
				first = min(ar1[i], ar2[j])
			if counter == n + 1:
				second = min(ar1[i], ar2[j])
			if min(ar1[i], ar2[j]) == ar1[i]:
				i += 1
			else:
				j += 1
		if second is None:
			if j < i:
				second = ar2[j]
			else:
				second = ar1[i]
		return first + second


class Solution:

	def findMidSum(self, ar1, ar2, n):
		if n == 1:
			return ar1[0] + ar2[0]
		l = []
		i = 0
		j = 0
		k = 0
		f = 0
		while i < n and j < n:
			if ar1[i] > ar2[j]:
				l.append(ar2[j])
				j += 1
			else:
				l.append(ar1[i])
				i += 1
			k += 1
			if k == n + 1:
				f = 1
				break
		while i < n and f == 0:
			l.append(ar1[i])
			i += 1
			k += 1
			if k == n + 1:
				break
		while j < n and f == 0:
			l.append(ar2[j])
			j += 1
			k += 1
			if k == n + 1:
				break
		return l[-1] + l[-2]