Search Element in a Rotated Sorted Array

Given a sorted array that has been rotated, the task is to find the index of a specific element. The array is initially sorted in ascending order and then rotated clockwise by an unknown amount.

For example, a sorted array [1, 2, 3, 4, 5] rotated by 2 positions becomes [4, 5, 1, 2, 3].

You are required to answer multiple queries where for each query, you will search a particular element and return its index if found; otherwise, return -1.

Your goal is to achieve this in O(logN) time complexity for each query.

Input:

N
A1 A2 A3 ... AN
Q
Q1
Q2
...
QQ

Output:

An integer representing the index of the searched element for each query, or -1 if the element is not found.

Example:

Input:

N = 5
A = 4 5 1 2 3
Q = 2
key = 1
key = 6

Output:

2
-1

Constraints:

• 1 <= N <= 10⁶
• -10⁹ <= A[i] <= 10⁹
• 1 <= Q <= 500
• -10⁹ <= Q[i] <= 10⁹
• Time Limit: 1 sec

Note:

You only need to return the result, as printing is handled elsewhere.