import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] searchRange(int[] nums, int target) {
        List<Integer> ans = findFirst(nums, target, 0, nums.length - 1, nums.length - 1);
        if(ans.size() == 0) {
            int[] a =  {-1,-1};
            return a;
        } else {
            int[] a = {ans.get(0), ans.get(1)};
            return a;
        }
    }

    public List<Integer> findFirst(int[] nums, int target, int begin, int end, int length) {
        int mid = (begin + end)/2;
        List<Integer> ans = new ArrayList();
        if(begin > end || (begin == end && target != nums[mid])) {
            return ans;
        } else if(target > nums[mid]){
            return findFirst(nums, target, mid+1, end, length);
        } else if(target < nums[mid]) {
            return findFirst(nums, target, begin, mid-1, length);
        } else {
            int right = mid;
            int left = mid;
            int lefts = mid;
            int rights = mid;
            System.out.println("Right");
            System.out.println("Left");
            System.out.println(mid);
            for(int i = 1 ; mid + i <= length; i = i*2) {
                System.out.println("Rights");
                if(nums[mid + i] == target) {
                    System.out.println("Rightss");
                    right = mid + i;
                    rights = right;
                    continue;
                } else break;


                /*else {
                    System.out.println("Right");
                    System.out.println(right);
                    while ((right <= length) && nums[right] == target) {
                        rights = right;
                        right++;
                    }
                    break;
                }*/
            }

            while ((right <= length) && nums[right] == target) {
                rights = right;
                right++;
            }
            for(int i = 1 ; mid - i  >= 0; i = i*2) {
                System.out.println("LeftLeft");
                System.out.println(left);
                if(nums[mid - i] == target) {
                    left = mid - i;
                    lefts = left;
                    System.out.println("Leftsss");
                    System.out.println(lefts);
                    continue;
                } else break;
                /*else {
                    System.out.println("Left");
                    System.out.println(left);
                    while ((left >= 0) && nums[left] == target) {
                        lefts = left;
                        left--;

                    }
                    break;
                }*/
            }

            while ((left >= 0) && nums[left] == target) {
                lefts = left;
                left--;

            }
            ans.add(lefts);
            ans.add(rights);
        }
        return ans;
    }
}