int bs(vector<int>a, int low, int high, int key)
{
    if (high < low)
    return -1;
  int mid = (low + high)/2;
  if (key == a[mid])
    return mid;
  if (key > a[mid])
    return bs(a, (mid + 1), high, key);
  return bs(a, low, (mid -1), key);
}

int findp(vector<int>a ,int low, int high)
{
    if(high==low)
        return high;
    if(high<low)
        return -1;
    int m = (low + high)/2;
    if (m < high && a[m] > a[m + 1])
        return m;
    if (m > low && a[m] < a[m - 1])
    return (m-1);

    if (a[low] >= a[m])
    return findp(a, low, m-1);

   return findp(a, m + 1, high);

}

int pbs(vector<int>a, int k)
{
int p = findp(a,0,a.size()-1);
int n = a.size();
if(p==-1)
    return bs(a,0,n-1,k);
if(a[p]==k)
    return p;
if(a[0]<=k)
    return bs(a,0,p-1,k);
return bs(a,p,n-1,k);
}