Given an array of n distinct elements. Check whether the given array is a k sorted array or not. A k sorted array is an array where each element is at most k distance away from its target position in the sorted array.
Example 1:
Input:
N=6
arr[] = {3, 2, 1, 5, 6, 4} 
K = 2
Output: Yes
Explanation:
Every element is at most 2 distance 
away from its target position in the
sorted array.  
Example 2:
Input:
N=7
arr[] = {13, 8, 10, 7, 15, 14, 12}
K = 1
Output: No
Your Task:
Since, 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 isKSortedArray() that takes array arr, integer n and integer k as parameters and return "Yes" if the array is a k sorted array else return "No".
Expected Time Complexity: O(NlogN).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ K ≤ N

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3

class Solution:
    def isKSortedArray(self, arr, n, k): 
        #code here.


Solutions:
class Solution:

	def isKSortedArray(self, arr, n, k):
		d = {}
		l = sorted(arr)
		for i in range(n):
			d[l[i]] = i
		for i in range(n):
			if abs(i - d[arr[i]]) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		arr = list(enumerate(arr))
		arr = sorted(arr, key=lambda x: x[1])
		for i in range(n):
			if abs(arr[i][0] - i) > k:
				return 'No'
		return 'Yes'


import heapq

class Solution:

	def isKSortedArray(self, arr, n, k):
		min_heap = []
		for i in range(n):
			heapq.heappush(min_heap, (arr[i], i))
		i = 0
		while min_heap:
			(x, idx) = heapq.heappop(min_heap)
			if abs(i - idx) > k:
				return 'No'
			i += 1
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		orig_idx = {arr[i]: i for i in range(n)}
		arr.sort()
		for i in range(n):
			if abs(i - orig_idx[arr[i]]) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		(l, a, k) = (arr, sorted(arr), k)
		d = {}
		for (i, j) in enumerate(l):
			d[j] = i
		for (i, j) in enumerate(a):
			if not (d[j] - k <= i and d[j] + k >= i):
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		dicti = {}
		lst = [i for i in arr]
		lst.sort()
		for i in range(n):
			if arr[i] not in dicti:
				dicti[arr[i]] = i
		for i in range(n):
			if abs(i - dicti[lst[i]]) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		a = sorted(arr)
		d = {}
		for i in range(n):
			d[a[i]] = i
		s = 0
		while s < n:
			if abs(d[arr[s]] - s) <= k:
				s += 1
			else:
				return 'No'
		return 'Yes'


def bs(arr, x):
	(st, en) = (0, len(arr) - 1)
	while st <= en:
		mid = (st + en) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			en = mid - 1
		else:
			st = mid + 1

class Solution:

	def isKSortedArray(self, arr, n, k):
		temp = sorted(arr)
		for i in range(n):
			pos = bs(temp, arr[i])
			if i - k <= pos <= i + k:
				continue
			return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		p = sorted(arr)
		d = {}
		for index in range(n):
			d.update({arr[index]: index}) if arr[index] not in d else None
		for index in range(n):
			elem = p[index]
			ind = d[elem]
			if abs(index - ind) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		c = 0
		u = []
		for i in range(len(arr)):
			u.append(arr[i])
		u = sorted(u)
		v = []
		h = {}
		t = {}
		e = []
		for j in range(len(arr)):
			h[arr[j]] = j
		for s in range(len(u)):
			t[u[s]] = s
		for x in h:
			e.append(abs(h[x] - t[x]))
		for r in range(len(e)):
			if e[r] <= k:
				c += 1
		if c == n:
			return 'Yes'
		else:
			return 'No'


class Solution:

	def isKSortedArray(self, arr, n, k):
		p = arr.copy()
		p.sort()
		for i in range(n):
			start = 0
			end = n - 1
			while start <= end:
				mid = start + (end - start) // 2
				if p[mid] == arr[i]:
					if abs(mid - i) > k:
						return 'No'
					break
				elif p[mid] > arr[i]:
					end = mid - 1
				else:
					start = mid + 1
		return 'Yes'


class Solution:

	def binarySearch(self, arr, low, high, x):
		while low <= high:
			mid = int((low + high) / 2)
			if arr[mid] == x:
				return mid
			elif arr[mid] > x:
				high = mid - 1
			else:
				low = mid + 1

	def isKSortedArray(self, arr, n, k):
		aux = [0 for i in range(n)]
		for i in range(0, n, 1):
			aux[i] = arr[i]
		aux.sort(reverse=False)
		for i in range(0, n, 1):
			j = self.binarySearch(aux, 0, n - 1, arr[i])
			if abs(i - j) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		temp = sorted(arr)
		table = {}
		table2 = {}
		for i in range(n):
			table[arr[i]] = i
			table2[temp[i]] = i
		for key in table:
			if abs(table[key] - table2[key]) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		a = arr[:]
		arr.sort()
		count = 0
		for i in range(n):
			l = 0
			h = n - 1
			while l <= h:
				mid = (l + h) // 2
				if a[i] == arr[mid]:
					if abs(mid - i) <= k:
						break
					else:
						return 'No'
				elif arr[mid] > a[i]:
					h = mid - 1
				else:
					l = mid + 1
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		li_copy = arr[:]
		li_copy.sort()
		for i in range(n):
			s = 0
			e = n - 1
			while s <= e:
				m = (s + e) // 2
				if li_copy[m] == arr[i]:
					if abs(m - i) <= k:
						break
					else:
						return 'No'
				elif li_copy[m] > arr[i]:
					e = m - 1
				else:
					s = m + 1
		return 'Yes'


import heapq

class Solution:

	def isKSortedArray(self, arr, n, k):
		min_heap = []
		i = 0
		ans = []
		for (i, x) in enumerate(arr):
			heapq.heappush(min_heap, (x, i))
		i = 0
		while len(min_heap):
			x = heapq.heappop(min_heap)
			if abs(x[1] - i) > k:
				return 'No'
			i += 1
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		dic = {}
		lis = arr.copy()
		lis.sort()
		for i in range(n):
			dic[lis[i]] = i
		for (i, ele) in enumerate(arr):
			if abs(dic[ele] - i) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		a = sorted(arr)

		def Binarysearch(a, x):
			l = 0
			h = n - 1
			while l <= h:
				mid = (l + h) // 2
				if a[mid] == x:
					return mid
				elif x < a[mid]:
					h = mid - 1
				else:
					l = mid + 1
		for i in range(n):
			if abs(i - Binarysearch(a, arr[i])) <= k:
				continue
			else:
				return 'No'
		return 'Yes'


import heapq as hq

class Solution:

	def isKSortedArray(self, arr, n, k):
		min_heap = []
		for i in range(n):
			hq.heappush(min_heap, (arr[i], i))
		i = 0
		while i < n and len(min_heap) > 0:
			(ele, ind) = hq.heappop(min_heap)
			if abs(ind - i) <= k:
				flag = 1
			else:
				flag = 0
				break
			i += 1
		if flag == 1:
			return 'Yes'
		else:
			return 'No'


class Solution:

	def isKSortedArray(self, arr, n, k):
		temp = []
		for i in range(len(arr)):
			temp.append((arr[i], i))
		arr.sort()
		temp.sort()
		dummy = []
		for i in range(len(arr)):
			dummy.append((arr[i], i))
		for i in range(len(arr)):
			if abs(dummy[i][1] - temp[i][1]) > k:
				return 'No'
		return 'Yes'


from bisect import bisect_left

class Solution:

	def isKSortedArray(self, arr, n, k):
		sorted_arr = sorted(arr)
		for i in range(n):
			j = bisect_left(sorted_arr, arr[i])
			if abs(i - j) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		dum_sort = [i for i in arr]
		dum_sort.sort()
		hash = {}
		for i in range(n):
			hash[dum_sort[i]] = i
		res = 1
		for i in range(len(arr)):
			if abs(hash[arr[i]] - i) > k:
				res = 0
				break
		if res == 0:
			return 'No'
		else:
			return 'Yes'


from heapq import heapify, heappush, heappop

class Solution:

	def isKSortedArray(self, arr, n, k):
		for i in range(n):
			arr[i] = i + arr[i] * n
		arr.sort()
		for i in range(n):
			if abs(arr[i] % n - i) > k:
				return 'No'
		return 'Yes'


class Solution:

	def binarysearch(self, arr, l, r, k):
		if l <= r:
			mid = (l + r) // 2
			if arr[mid] == k:
				return mid
			elif arr[mid] < k:
				return self.binarysearch(arr, mid + 1, r, k)
			else:
				return self.binarysearch(arr, l, mid - 1, k)
		return -1

	def isKSortedArray(self, arr, n, k):
		arr2 = arr.copy()
		arr2.sort()
		for i in range(n):
			l = self.binarysearch(arr2, 0, n, arr[i])
			if abs(l - i) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		orgarr = [0] * n
		for i in range(0, n):
			orgarr[i] = arr[i]
		arr.sort()
		for i in range(0, n):
			indi = self.binarysearch(arr, n, orgarr[i])
			if abs(i - indi) > k:
				return 'No'
		return 'Yes'

	def binarysearch(self, arr, n, target):
		start = 0
		end = len(arr) - 1
		while start <= end:
			mid = start + (end - start) // 2
			if arr[mid] == target:
				return mid
			elif arr[mid] < target:
				start = mid + 1
			else:
				end = mid - 1
		return -1


import heapq

class Solution:

	def isKSortedArray(self, arr, n, k):
		heap = []
		for i in range(k + 1):
			heapq.heappush(heap, (arr[i], i))
		j = 0
		for i in range(k + 1, n):
			val = heapq.heappop(heap)
			if j - val[1] > k:
				return 'No'
			heapq.heappush(heap, (a[i], i))
			a[j] = val[0]
			j += 1
		while len(heap) != 0:
			val = heapq.heappop(heap)
			if j - val[1] > k:
				return 'No'
			a[j] = val[0]
			j += 1
		for i in range(len(a) - 1):
			if a[i] > a[i + 1]:
				return 'No'
		return 'Yes'


class Solution:

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

		def binary_search(arr, n, x):
			low = 0
			high = n - 1
			while low <= high:
				mid = (low + high) // 2
				if arr[mid] == x:
					return mid
				elif arr[mid] > x:
					high = mid - 1
				else:
					low = mid + 1
			return -1
		new_arr = sorted(arr)
		for i in range(n):
			bin = binary_search(new_arr, len(new_arr), arr[i])
			diff = abs(bin - i)
			if diff > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		hashMap = dict()
		for (idx, val) in enumerate(arr):
			hashMap[val] = idx
		arr.sort()
		for (idx, ele) in enumerate(arr):
			if abs(idx - hashMap[ele]) > k:
				return 'No'
		return 'Yes'


class Solution:

	def binarysearch(self, sarr, x):
		low = 0
		high = len(sarr) - 1
		while low <= high:
			mid = (low + high) // 2
			if sarr[mid] == x:
				return mid
			elif sarr[mid] < x:
				low = mid + 1
			else:
				high = mid - 1

	def isKSortedArray(self, arr, n, k):
		arr1 = []
		arr1[:] = arr
		arr.sort()
		for i in range(len(arr1)):
			j = self.binarysearch(arr, arr1[i])
			if abs(i - j) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		brr = arr[0:]
		brr.sort()
		for i in range(n):
			start = 0
			end = n - 1
			x = arr[i]
			while start <= end:
				mid = start + (end - start) // 2
				if brr[mid] == x:
					if mid > i and mid - i > k:
						return 'No'
					elif mid < i and i - mid > k:
						return 'No'
					break
				elif brr[mid] > x:
					end = mid - 1
				else:
					start = mid + 1
		return 'Yes'


class Solution:

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

		def binary_search(arr, low, high, ele):
			while low <= high:
				mid = (low + high) // 2
				if arr[mid] == ele:
					return mid
				elif arr[mid] > ele:
					high = mid - 1
				else:
					low = mid + 1
		aux = [0 for i in range(n)]
		for i in range(n):
			aux[i] = arr[i]
		aux.sort()
		for i in range(n):
			j = binary_search(aux, 0, n - 1, arr[i])
			if abs(i - j) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		res = [[arr[i], i] for i in range(len(arr))]
		res.sort()
		for i in range(n):
			if abs(i - res[i][1]) > k:
				return 'No'
		return 'Yes'


from collections import defaultdict

class Solution:

	def isKSortedArray(self, arr, n, k):
		Dict = defaultdict()
		for i in range(len(arr)):
			Dict[arr[i]] = [i]
		arr.sort(reverse=False)
		for i in range(len(arr)):
			Dict[arr[i]].append(i)
		for key in Dict:
			if abs(Dict[key][0] - Dict[key][1]) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		arr2 = sorted(arr)
		for i in range(len(arr)):
			s = 0
			e = len(arr) - 1
			mid = (s + e) // 2
			ans = 0
			while s <= e:
				if arr2[mid] == arr[i]:
					ans = mid
					break
				elif arr2[mid] > arr[i]:
					e = mid - 1
				elif arr2[mid] < arr[i]:
					s = mid + 1
				mid = (s + e) // 2
			if abs(ans - i) > k:
				return 'No'
		return 'Yes'


class Solution:

	def binary_search(self, arr, target):
		low = 0
		high = n - 1
		while low <= high:
			mid = low + (high - low) // 2
			if arr[mid] == target:
				return mid
			elif arr[mid] > target:
				high = mid - 1
			else:
				low = mid + 1

	def isKSortedArray(self, arr, n, k):
		temp = arr[:]
		temp.sort()
		for i in range(n):
			pos = self.binary_search(temp, arr[i])
			if k < abs(i - pos):
				return 'No'
		return 'Yes'


import copy

class Solution:

	def isKSortedArray(self, arr, n, k):
		kt = {}
		j = 0
		for x in arr:
			kt[x] = j
			j += 1
		arr.sort()
		i = 0
		for x in arr:
			if abs(i - kt[x]) > k:
				return 'No'
			else:
				i += 1
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		e = {}
		for i in range(n):
			b = arr[i]
			e[b] = i
		x = sorted(arr)
		d = {}
		for i in range(n):
			a = x[i]
			d[a] = i
		for i in range(n):
			c = arr[i]
			y = e[c]
			z = d[c]
			if abs(y - z) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		sorted_arr = [(i, arr[i]) for i in range(len(arr))]
		sorted_arr.sort(key=lambda x: x[1])
		for i in range(len(arr)):
			if abs(i - sorted_arr[i][0]) > k:
				return 'No'
		return 'Yes'


class Solution:

	def binary_search(self, arr, lo, hi, target):
		if lo < 0:
			lo = 0
		if hi > n - 1:
			hi = n - 1
		while lo <= hi:
			mid = (lo + hi) // 2
			if arr[mid] == target:
				return True
			elif arr[mid] < target:
				lo = mid + 1
			else:
				hi = mid - 1
		return False

	def isKSortedArray(self, temp, n, k):
		arr = sorted(temp)
		for i in range(n):
			x = Solution().binary_search(arr, i - k, i + k, temp[i])
			if x == False:
				return 'No'
		return 'Yes'
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	ob = Solution()
	print(ob.isKSortedArray(a, n, k))


class Solution:

	def isKSortedArray(self, arr, n, k):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		arr.sort()
		flag = 'Yes'
		for i in range(n):
			if abs(i - d[arr[i]]) > k:
				flag = 'No'
				break
		return flag
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	ob = Solution()
	print(ob.isKSortedArray(a, n, k))


class Solution:

	def isKSortedArray(self, arr, n, k):
		arrCopy = list(arr)
		arrCopy.sort()
		for (index, num) in enumerate(arr):
			sortedIndex = self.bSearch(num, arrCopy, 0, n - 1)
			if abs(index - sortedIndex) > k:
				return 'No'
		return 'Yes'

	def bSearch(self, target, arr, start, end):
		if end < start:
			return -1
		mid = start + (end - start) // 2
		if arr[mid] == target:
			return mid
		elif arr[mid] < target:
			return self.bSearch(target, arr, mid + 1, end)
		else:
			return self.bSearch(target, arr, start, mid - 1)
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	ob = Solution()
	print(ob.isKSortedArray(a, n, k))


class Solution:

	def isKSortedArray(self, arr, n, k):
		arrCopy = list(arr)
		arrCopy.sort()
		arrMap = dict()
		for (index, num) in enumerate(arrCopy):
			arrMap[num] = index
		for (index, num) in enumerate(arr):
			if abs(index - arrMap[num]) > k:
				return 'No'
		return 'Yes'
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	ob = Solution()
	print(ob.isKSortedArray(a, n, k))


class Solution:

	def binary(self, arr, n, t):
		left = 0
		right = n - 1
		while left <= right:
			mid = left + (right - left) // 2
			if t == arr[mid]:
				return mid
			elif t < arr[mid]:
				right = mid - 1
			else:
				left = mid + 1
		return -1

	def isKSortedArray(self, arr, n, k):
		arr = list(enumerate(arr))
		arr = sorted(arr, key=lambda x: x[1])
		for i in range(n):
			if abs(arr[i][0] - i) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, a, n, k):
		l = list(enumerate(a))
		a.sort()
		l.sort(key=lambda x: x[1])
		for i in range(n):
			if abs(i - l[i][0]) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		arr1 = arr.copy()
		arr1.sort()
		dic1 = {}
		dic2 = {}
		for i in range(n):
			dic1[arr[i]] = i
			dic2[arr1[i]] = i
		for i in range(n):
			if abs(dic1[arr[i]] - dic2[arr[i]]) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, a, n, k):
		hash_map = {}
		for i in range(n):
			hash_map[a[i]] = i
		a.sort()
		for i in range(n):
			diff = abs(hash_map[a[i]] - i)
			if diff > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray2(self, arr, n, k):
		arr2 = sorted(arr[:])
		check = 0
		if arr:
			for (position, element) in enumerate(arr):
				if abs(arr2.index(element) - arr.index(element)) <= k:
					check += 1
					if check == n:
						return 'Yes'
		return 'No'

	def isKSortedArray(self, arr, n, k):
		arr = list(enumerate(arr))
		arr = sorted(arr, key=lambda x: x[1])
		for i in range(n):
			if abs(arr[i][0] - i) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		x = []
		for i in range(n):
			x.append([arr[i], i])
		x.sort()
		for i in range(n):
			if abs(i - x[i][1]) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		sortedArr = [val for val in arr]
		sortedArr.sort()
		for i in range(n):
			x = arr[i]
			low = 0
			high = n - 1
			pos = -1
			while low < high:
				mid = (low + high) // 2
				if sortedArr[mid] == x:
					pos = mid
					break
				elif sortedArr[mid] < x:
					low = mid + 1
				else:
					high = mid - 1
			if pos == -1:
				pos = low
			if abs(pos - i) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		sarr = [0] * n
		for i in range(0, n):
			sarr[i] = arr[i]
		sarr.sort()
		d = {}
		for i in range(0, n):
			d[sarr[i]] = i
		for i in range(0, n):
			if abs(i - d[arr[i]]) > k:
				return 'No'
		return 'Yes'


class Solution:

	def BinarySearch(self, arr, k):
		start = 0
		end = len(arr) - 1
		mid = (start + end) // 2
		while start <= end:
			if arr[mid] == k:
				return mid
			elif arr[mid] < k:
				start = mid + 1
			else:
				end = mid - 1
			mid = (start + end) // 2
		return False

	def isKSortedArray(self, arr, n, k):
		arr2 = sorted(arr)
		for i in range(len(arr)):
			if abs(i - self.BinarySearch(arr2, arr[i])) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		arr_dict = {}
		i = 0
		while i < n:
			arr_dict[arr[i]] = i
			i = i + 1
		arr.sort()
		i = 0
		while i < n:
			idx1 = i
			idx2 = arr_dict[arr[i]]
			if abs(idx1 - idx2) > k:
				return 'No'
			i = i + 1
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		valToIndex = {}
		for (i, el) in enumerate(arr):
			valToIndex[el] = i
		arr.sort()
		for (i, el) in enumerate(arr):
			if abs(i - valToIndex[el]) > k:
				return 'No'
		return 'Yes'


import heapq

class Solution:

	def isKSortedArray(self, arr, n, k):
		h = []
		heapq.heapify(h)
		ans = {}
		for i in range(n):
			ans[arr[i]] = i
		arr.sort()
		for i in range(n):
			if abs(i - ans[arr[i]]) > k:
				return 'No'
		return 'Yes'


class Solution:

	def b_search(self, arr, target, n):
		low = 0
		high = n - 1
		while low <= high:
			mid = low + (high - low) // 2
			if arr[mid] == target:
				return mid
			elif arr[mid] > target:
				high = mid - 1
			else:
				low = mid + 1
		return -1

	def isKSortedArray(self, arr, n, k):
		sorted_arr = sorted(a)
		for i in range(n):
			pos_in_sorted = self.b_search(sorted_arr, arr[i], n)
			if not abs(pos_in_sorted - i) <= k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		_sortedArr = sorted(arr)
		_sortedDict = {}
		for i in range(n):
			_sortedDict[_sortedArr[i]] = i
		for i in range(n):
			if abs(i - _sortedDict[arr[i]]) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		D = {}
		for i in range(0, n):
			D[arr[i]] = i
		A = sorted(arr)
		for i in range(0, n):
			if abs(D[A[i]] - i) > k:
				return 'No'
		return 'Yes'


class Solution:

	def isKSortedArray(self, arr, n, k):
		di = {}
		di2 = {}
		count = 0
		for i in range(len(arr)):
			di[arr[i]] = i
		arr.sort()
		for i in range(len(arr)):
			di2[arr[i]] = i
		for (i, j) in di.items():
			if abs(di2[i] - j) <= k:
				count += 1
			else:
				return 'No'
		return 'Yes'


from heapq import *
import math

class Solution:

	def isKSortedArray(self, arr, n, k):
		s = sorted(arr)
		d = {}
		for i in range(len(arr)):
			d[arr[i]] = i
		for i in range(len(arr)):
			if abs(d[s[i]] - i) > k:
				return 'No'
		return 'Yes'