Given an array arr[] of N integers which may contain duplicate elements, the index of an element of this array is given to us, the task is to find the final position of this element ( for which the index is given) in the array after the stable sort is applied on the array. 
 
Example 1:
Input: N = 10, INDEX = 5
arr[]= {3, 4, 3, 5, 2, 3, 4, 3, 1, 5}
Output: 4
Explanation: Element initial index – 5 
(third 3) After sorting array by stable 
sorting algorithm,we get array as shown 
below [1(8), 2(4), 3(0), 3(2), 3(5), 3(7),
4(1), 4(6), 5(3), 5(9)] with their 
initial indices shown in parentheses next 
to them,Element's index after sorting = 4.
 
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function getIndexInSortedArray() that takes array arr, integer N, and integer index as parameters and returns the number of uneaten leaves.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: class Solution:

    def getIndexInSortedArray(self, arr, n, k):

        # Your code goes here

Solutions:
class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		count = 0
		e = arr[k]
		for i in range(k):
			if arr[i] == e:
				count += 1
		for i in range(n):
			if arr[i] < e:
				count += 1
		return count


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		index = [i for i in range(n)]
		ans = zip(arr, index)
		ans = sorted(ans)
		for i in range(n):
			if ans[i][1] == k:
				return i


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		elem = arr[k]
		add = arr[:k].count(elem)
		arr.sort()
		sort_ind = arr.index(elem)
		return sort_ind + add


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		ele = arr[k]
		cou = 0
		for i in range(k):
			if arr[i] == ele:
				cou += 1
		arr.sort()
		ans = arr.index(ele)
		return ans + cou


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		target = arr[k]
		count_lesser = 0
		count_equal = 0
		for i in range(n):
			if arr[i] < target:
				count_lesser += 1
			if arr[i] == target and i < k:
				count_equal += 1
		return count_lesser + count_equal


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		indv = arr[k]
		c = 0
		for i in range(k):
			if arr[i] == indv:
				c = c + 1
		arr.sort()
		res = arr.index(indv)
		res1 = res + c
		return res1


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		result = 0
		for i in range(n):
			if arr[i] < arr[k]:
				result += 1
			if arr[i] == arr[k] and i < k:
				result += 1
		return result


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		count = 0
		Arr = []
		K = arr[k]
		for i in range(k):
			if arr[i] == arr[k]:
				count += 1
		arr.sort()
		for i in range(n):
			if arr[i] != K:
				Arr.append(arr[i])
			elif Arr.count(K) == count:
				return i
			else:
				Arr.append(arr[i])


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		l = [[arr[i], i] for i in range(len(arr))]
		l = sorted(l)
		for i in range(len(l)):
			if l[i][1] == k:
				return i


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		index_value = arr[k]
		c = 0
		for i in range(k):
			if arr[i] == index_value:
				c += 1
		arr.sort()
		res = arr.index(index_value)
		final = res + c
		return final


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		res = arr[k]
		s = 0
		e = 0
		for i in range(n):
			if arr[i] < res:
				s += 1
			if i < k and res == arr[i]:
				e += 1
		return s + e


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		pos = 0
		i = 0
		while i < n:
			if i < k:
				if arr[i] <= arr[k]:
					pos += 1
			elif arr[i] < arr[k]:
				pos += 1
			i += 1
		return pos


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		for i in range(n):
			arr[i] = [arr[i], i]
		arr.sort()
		for i in range(n):
			if arr[i][1] == k:
				return i


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		ele = arr[k]
		smallEle = 0
		eqEleBeforeIdx = 0
		for i in range(n):
			if arr[i] < ele:
				smallEle += 1
			if i < k and ele == arr[i]:
				eqEleBeforeIdx += 1
		return smallEle + eqEleBeforeIdx


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		num = arr[k]
		c = 0
		for i in range(n):
			if arr[i] < num or (arr[i] == num and i < k):
				c += 1
		return c


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		x = []
		z = []
		for i in range(n):
			x.append((arr[i], i))
		y = sorted(x)
		for (i, j) in y:
			z.append(j)
		for i in range(n):
			if z[i] == k:
				return i


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		ele = arr[k]
		s = 0
		q = 0
		for i in range(k):
			if ele == arr[i]:
				s = s + 1
		arr.sort()
		for i in range(n):
			if arr[i] == ele:
				if q == s:
					return i
				q = q + 1


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		l = []
		for i in range(n):
			l.append([arr[i], i])
		l.sort(key=lambda x: x[0])
		for i in range(n):
			if l[i][1] == k:
				return i


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		a = arr[k]
		c = 0
		c1 = 0
		for i in range(k + 1):
			if arr[i] == a:
				c += 1
		arr.sort()
		for i in range(len(arr)):
			if arr[i] == a:
				c1 += 1
				if c == c1:
					return i


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		count = -1
		ele = arr[k]
		for i in range(n):
			if ele > arr[i]:
				count += 1
			if ele == arr[i] and i <= k:
				count += 1
		return count


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		c = 0
		for i in range(k + 1):
			if arr[i] == arr[k]:
				c += 1
		key = arr[i]
		ind = -1
		j = 0
		count = 0
		arr.sort()
		while count != c:
			if arr[j] == key:
				count += 1
			j += 1
		return j - 1


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		a = [i[0] for i in sorted(enumerate(arr), key=lambda x: x[1])]
		return a.index(k)


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		m = arr[k]
		arr1 = arr[:k + 1]
		ct = arr1.count(m)
		arr.sort()
		res = arr.index(m) + ct - 1
		return res


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		c = 0
		key = arr[k]
		for x in arr[:k]:
			if x <= key:
				c += 1
		for x in arr[k + 1:]:
			if key > x:
				c += 1
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		l = list(map(int, input().split()))
		n = l[0]
		k = l[1]
		a = list(map(int, input().split()))
		ob = Solution()
		ans = ob.getIndexInSortedArray(a, n, k)
		print(ans)


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		l = []
		for i in range(n):
			l.append([arr[i], i])
		l.sort(key=lambda x: x[0])
		b = []
		for i in range(n):
			if l[i][1] == k:
				return i
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		l = list(map(int, input().split()))
		n = l[0]
		k = l[1]
		a = list(map(int, input().split()))
		ob = Solution()
		ans = ob.getIndexInSortedArray(a, n, k)
		print(ans)


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		indx1 = 0
		sno = 0
		ele = arr[k]
		for itr in range(k + 1):
			if ele == arr[itr]:
				sno += 1
		arr.sort()
		count = 0
		for itr in range(n):
			if arr[itr] == ele:
				count += 1
				if count == sno:
					return itr
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		l = list(map(int, input().split()))
		n = l[0]
		k = l[1]
		a = list(map(int, input().split()))
		ob = Solution()
		ans = ob.getIndexInSortedArray(a, n, k)
		print(ans)


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		K = [arr[k], k]
		A = []
		for i in range(n):
			A.append([arr[i], i])
		A.sort()
		return A.index(K)


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		count = 0
		small = 0
		val = arr[k]
		for i in range(0, len(a)):
			if val == arr[i] and i <= k:
				count += 1
			if arr[i] < val:
				small += 1
		return small + count - 1


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		ans = 0
		el = arr[k]
		for i in range(n):
			if i < k and arr[i] <= el:
				ans += 1
			elif arr[i] < el:
				ans += 1
		return ans


class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		pos = 0
		for i in range(n):
			if i < k:
				if arr[i] <= arr[k]:
					pos += 1
			elif arr[i] < arr[k]:
				pos += 1
		return pos


def search(arr, l, r, x):
	if r >= l:
		mid = l + (r - l) // 2
		if arr[mid] >= x:
			return search(arr, l, mid - 1, x)
		else:
			return search(arr, mid + 1, r, x)
	return l

class Solution:

	def getIndexInSortedArray(self, arr, n, k):
		x = arr[k]
		y = arr[:k].count(x)
		arr.sort()
		return search(arr, 0, n - 1, x) + y