Search in Rotated Sorted Array

You are given a rotated sorted array and a target value. Write a function that searches for the target in the array and returns its index if found, or -1 if not found. There may be duplicates present in the array. Input format: First line contains integer n (size of the array). Second line contains n integers (the elements of the rotated sorted array). Third line contains the target integer. Output format: An integer representing the index of the target or -1. Example: Input: 7 2 5 6 0 0 1 2 0 Output: 3