Problem: Search In Rotated Sorted Array

Given a sorted array that has been rotated clockwise by an unknown amount, you need to answer Q queries. Each query is represented by an integer Q[i], and you must determine if this integer exists in the rotated array. Return the index if found, otherwise return -1.

Input:

The first line contains an integer N, representing the size of the array.
The second line contains N space-separated integers, representing the elements of the array A.
The third line contains an integer Q, representing the number of queries.
The next Q lines each contain a single integer Q[i], the number to search for in the array.

Output:

For each query, output the index of the number if found; otherwise, output -1. Each output should be on a new line.

Example:

Input:
N = 5
A = [4, 5, 6, 7, 0, 1, 2]
Q = 3
Q[i] = [0, 3, 6]

Output:
4
-1
2

Constraints:

• 1 ≤ N ≤ 10^6
• -10^9 ≤ A[i] ≤ 10^9
• 1 ≤ Q ≤ 500
• -10^9 ≤ Q[i] ≤ 10^9
• Time Limit: 1 sec

Note:

The problem requires solving each query in O(logN) time complexity.