#include <cassert>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using std::vector, std::string;

template<typename T>
int partition(vector<T>& v, int left, int right) {
    int mid = (left+right)/2;
    while (left <= right) {
        while (v[left] < v[mid])
            left++;
        while (v[right] > v[mid])
            right--;
        if (left < right) {
            T b = v[left];
            v[left] = v[right];
            v[right] = b;
            left++;
            right--;
        } else if (left == right) {
            break;
        }
    }
    return left;
}

template<typename T>
void quicksort(vector<T>& v, int start=0, int end=-1) {
    if (end < 0)
        end = v.size()-1;
    if (end-start < 2)
        return;

    int mid = partition(v, start, end);
    quicksort(v, start, mid);
    quicksort(v, mid, end);
}

template<typename T>
void quicksort2(vector<T>& v, int start=0, int end=-1) {
    if (end < 0)
        end = v.size()-1;

    int mid = partition(v, start, end);
    if (mid-1 > start)
        quicksort(v, start, mid);
    if (end > mid)
        quicksort(v, mid, end);
}

template<typename T>
void merge(vector<T>& v, int vlen, vector<T>& w) {
    // v must have space for w.
    assert(v.size()-vlen >= w.size());

    // Pointers to individual arrays.
    int a = vlen-1, b = w.size()-1;
    int i = v.size()-1;

    while (i >= 0) {
        if (v[a] >= w[b]) {
            v[i] = v[a];
            a--;
        } else {
            v[i] = w[b];
            b--;
        }
        i--;
    }

}

void sort_anagram(vector<string>& in) {
    std::sort(in.begin(), in.end(), [](string a, string b) {
            std::sort(a.begin(), a.end());
            std::sort(b.begin(), b.end());
            return a < b;
            });
}

template<typename T>
int shifted_binary_search(const vector<T>& v, const T& elem, int start=0, int end=-1, int off=-1) {
    if (end < 0)
        end = v.size()-1;
    // end is past-the-last element.
    
    if (off < 0) {
        // First find offset.
        int lo = start, mid = (start+end)/2, hi = end;

        while (lo < mid) {
            if (v[mid] > v[hi]) {
                lo = mid;
                mid = (lo+hi)/2;
                continue;
            } else if (v[lo] > v[mid]) {
                hi = mid;
                mid = (lo+hi)/2;
                continue;
            } else {
                break;
            }
        }
        return hi;
    }
}

int main(void) {
    vector<string> v{"hello", "olleh", "abc", "bca", "world", "wrlod"};

    std::cout << shifted_binary_search({5,6,1,2,3}, 1) << "\n";

    for (const auto& a : v)
        std::cout << a << " ";
    std::cout << "\n";
    return 0;
}