Given an array Arr[] of N elements. Perform K right circular rotations on given ranges [L...R]. After performing these rotations, we need to find element at a given index X.
Example 1:
Input:
N = 5, X = 1, K = 2
Arr[] = {1, 2, 3, 4, 5}
Ranges[][] = {{0, 2}, {0, 3}}
Output: 3
Explanation: Rotating the elements in range 
0-2 and 0-3, we have array as 4 3 1 2 5. 
Element at first position is 3.
Example 2:
Input:
N = 3, X = 2, K = 1
Arr[] = {1, 2, 3}
Ranges[][] = {{0, 1}}
Output: 3
Your Task:
You don't need to read input or print anything. Your task is to complete the function findElement() which takes the array of integers arr, n, x, ranges and k as parameters and returns an integer denoting the answer.
Expected Time Complexity: O(K)
Expected Auxiliary Space: O(1)
Constraints:
2 <= N <= 10^{5}
1 <= Arr[i] <= 10^{5}
1 <= K <= 10^{5}
X < N
0 <= L <= R

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution:
    def findElement(self, a, n, x, ranges, k):
        # code here

Solutions:
class Solution:

	def findElement(self, a, n, x, ranges, k):
		for i in range(k - 1, -1, -1):
			if x > ranges[i][0] and x <= ranges[i][1]:
				x -= 1
			elif x == ranges[i][0]:
				x = ranges[i][1]
		return a[x]


class Solution:

	def findElement(self, a, n, x, ranges, k):
		idx = k - 1
		ansIdx = x
		while idx >= 0:
			(l, r) = ranges[idx]
			if l <= ansIdx <= r:
				ansIdx -= 1
				if ansIdx < l:
					ansIdx = r
			idx -= 1
		return a[ansIdx]


class Solution:

	def findElement(self, a, n, x, ranges, k):
		for i in range(k - 1, -1, -1):
			left = ranges[i][0]
			right = ranges[i][1]
			if left <= x <= right:
				if x == left:
					x = right
				else:
					x = x - 1
		return a[x]


class Solution:

	def findElement(self, a, n, x, ranges, k):
		for i in range(k - 1, -1, -1):
			left = ranges[i][0]
			right = ranges[i][1]
			if left <= x <= right:
				if x == left:
					x = right
				else:
					x = x - 1
		return a[x]
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, x, k) = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		ranges = [[0 for i in range(2)] for j in range(k)]
		inputLine = list(map(int, input().strip().split()))
		kt = 0
		for i in range(k):
			for j in range(2):
				ranges[i][j] = inputLine[kt]
				kt += 1
		ans = Solution().findElement(arr, n, x, ranges, k)
		print(ans)
		tc -= 1


class Solution:

	def findElement(self, a, n, x, ranges, k):
		for index in range(k - 1, -1, -1):
			if x >= ranges[index][0] and x <= ranges[index][1]:
				if x == ranges[index][0]:
					x = ranges[index][1]
				else:
					x -= 1
		return a[x % n]


class Solution:

	def findElement(self, a, n, x, ranges, k):
		for r in ranges[::-1]:
			left = r[0]
			right = r[1]
			if left <= x and x <= right:
				if x == left:
					x = right
				else:
					x = x - 1
		return a[x]


class Solution:

	def findElement(self, a, n, x, ranges, k):
		Index = x
		for i in range(len(ranges) - 1, -1, -1):
			if Index >= ranges[i][0] and Index <= ranges[i][1]:
				length = ranges[i][1] - ranges[i][0] + 1
				Index = ranges[i][0] + (Index - ranges[i][0] - 1 + length) % length
		return a[Index]


class Solution:

	def findElement(self, a, n, x, ranges, k):
		while k > 0:
			k = k - 1
			range = ranges[k]
			if x >= range[0] and x <= range[1]:
				x = x - 1
				if x < range[0]:
					x = range[1]
		return a[x]


class Solution:

	def findElement(self, arr, n, index, ranges, rotations):
		for i in range(rotations - 1, -1, -1):
			left = ranges[i][0]
			right = ranges[i][1]
			if left <= index and right >= index:
				if index == left:
					index = right
				else:
					index = index - 1
		return arr[index]


class Solution:

	def findElement(self, a, n, x, ranges, k):
		for i in range(k - 1, -1, -1):
			l = ranges[i][0]
			r = ranges[i][1]
			if x >= l and x <= r:
				if x == l:
					x = r
				else:
					x = x - 1
		return a[x]


class Solution:

	def findElement(self, arr, n, x, ranges, k):
		for i in range(len(ranges) - 1, -1, -1):
			(l, r) = (ranges[i][0], ranges[i][1])
			if x == l:
				x = r
			elif x > l and x <= r:
				x -= 1
		return arr[x]


class Solution:

	def findElement(self, a, n, x, ranges, k):
		for r in ranges[::-1]:
			if x == r[0]:
				x = r[1]
			elif r[0] <= x <= r[1]:
				x -= 1
		return a[x]


class Solution:

	def findElement(self, arr, n, x, ranges, k):
		l = len(ranges)
		for i in range(l - 1, -1, -1):
			r = ranges[i]
			left = r[0]
			right = r[1]
			if x >= left and x <= right:
				if x == left:
					x = right
				else:
					x -= 1
		return arr[x]


class Solution:

	def findElement(self, a, n, x, ranges, k):
		n = x
		for i in range(k - 1, -1, -1):
			c = ranges[i][0]
			d = ranges[i][1]
			if c <= n and d >= n:
				if c == n:
					n = d
				else:
					n = n - 1
		return a[n]


class Solution:

	def findElement(self, a, n, x, ranges, k):
		index = x
		for r1 in range(len(ranges) - 1, -1, -1):
			l = ranges[r1][0]
			r = ranges[r1][1]
			if l <= index and index <= r:
				if index == l:
					index = r
				else:
					index = index - 1
		return a[index]