#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findMin(vector<int> & arr) {
int low = 0;
int high = arr.size() - 1;
while (arr[low] > arr[high]) {
int mid = (low + high) >> 1;
if (arr[mid] > arr[high]) {
low = mid + 1;
} else {
high = mid;
}
}
return arr[low];
}
int main() {
vector<int> a = {1,2,3,5,6,7,8,9,10};
rotate(a.begin(), a.begin() + 4, a.end());
for (int & i : a) cout << i << " ";
cout << endl;
cout << "Min is " << min(a[0], *is_sorted_until(a.begin(), a.end())) << endl;
cout << "Min is " << findMin(a) << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBmaW5kTWluKHZlY3RvcjxpbnQ+ICYgYXJyKSB7CiAgICBpbnQgbG93ID0gMDsKICAgIGludCBoaWdoID0gYXJyLnNpemUoKSAtIDE7CiAgICB3aGlsZSAoYXJyW2xvd10gPiBhcnJbaGlnaF0pIHsKICAgICAgICBpbnQgbWlkID0gKGxvdyArIGhpZ2gpID4+IDE7CiAgICAgICAgaWYgKGFyclttaWRdID4gYXJyW2hpZ2hdKSB7CiAgICAgICAgICAgIGxvdyA9IG1pZCArIDE7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgaGlnaCA9IG1pZDsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gYXJyW2xvd107Cn0KCmludCBtYWluKCkgewoJdmVjdG9yPGludD4gYSA9IHsxLDIsMyw1LDYsNyw4LDksMTB9OwoJcm90YXRlKGEuYmVnaW4oKSwgYS5iZWdpbigpICsgNCwgYS5lbmQoKSk7Cglmb3IgKGludCAmIGkgOiBhKSBjb3V0IDw8IGkgPDwgIiAiOwoJY291dCA8PCBlbmRsOwoJY291dCA8PCAiTWluIGlzICIgPDwgbWluKGFbMF0sICppc19zb3J0ZWRfdW50aWwoYS5iZWdpbigpLCBhLmVuZCgpKSkgPDwgZW5kbDsKCQoJY291dCA8PCAiTWluIGlzICIgPDwgZmluZE1pbihhKSA8PCBlbmRsOwoJcmV0dXJuIDA7Cn0=