/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
{
if(line==null || line.length()<=0){
return;
}
String[] tokens
= line.
trim().
split("\\s+"); int[] arr = new int[tokens.length];
for(int i=0;i<tokens.length;i++){
arr
[i
] = Integer.
parseInt(tokens
[i
]); }
Ideone ai = new Ideone();
int highIndex = ai.highestElem(arr, 0, arr.length-1);
int search
= Integer.
parseInt(br.
readLine()); //System.out.println(highIndex);
if(search>arr[highIndex]){
return;
}
int s = -1;
if(highIndex!=0&&arr[0]<=search){
s = ai.bS(arr, 0, highIndex, false, search);
if(s!=-1){
return;
}
}
if(highIndex!=arr.length&&arr[arr.length-1]<=search){
s = ai.bS(arr, highIndex+1, arr.length-1, true, search);
if(s!=-1){
return;
}
}
}
public int bS(int[] a, int low, int high, boolean rev, int val){
if(low>high){
return -1;
}
int mid = (low+high)/2;
if(a[mid]==val){
return mid;
}
if(a[mid]>val){
if(rev){
return bS(a, mid+1, high, rev, val);
}else{
return bS(a, low, mid-1, rev, val);
}
}
if(rev){
return bS(a, low, mid-1, rev, val);
}else{
return bS(a, mid+1, high, rev, val);
}
}
public int highestElem(int[] a, int low, int high){
if(low==high){
return low;
}
if(high-low==1){
return a[low]>a[high]?low:high;
}
int mid = (high+low)/2;
if(a[mid]<a[mid+1]){
return highestElem(a, mid+1, high);
}
if(a[mid-1]>a[mid]){
return highestElem(a, low, mid-1);
}
return mid;
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCUJ1ZmZlcmVkUmVhZGVyIGJyID0gbmV3IEJ1ZmZlcmVkUmVhZGVyKG5ldyBJbnB1dFN0cmVhbVJlYWRlcihTeXN0ZW0uaW4pKTsKCQlTdHJpbmcgbGluZSA9IGJyLnJlYWRMaW5lKCk7CgkJaWYobGluZT09bnVsbCB8fCBsaW5lLmxlbmd0aCgpPD0wKXsKCQkJcmV0dXJuOwoJCX0KCQlTdHJpbmdbXSB0b2tlbnMgPSBsaW5lLnRyaW0oKS5zcGxpdCgiXFxzKyIpOwoJCWludFtdIGFyciA9IG5ldyBpbnRbdG9rZW5zLmxlbmd0aF07CgkJZm9yKGludCBpPTA7aTx0b2tlbnMubGVuZ3RoO2krKyl7CgkJCWFycltpXSA9IEludGVnZXIucGFyc2VJbnQodG9rZW5zW2ldKTsKCQl9CgkJSWRlb25lIGFpID0gbmV3IElkZW9uZSgpOwoJCWludCBoaWdoSW5kZXggPSBhaS5oaWdoZXN0RWxlbShhcnIsIDAsIGFyci5sZW5ndGgtMSk7CgkJaW50IHNlYXJjaCA9IEludGVnZXIucGFyc2VJbnQoYnIucmVhZExpbmUoKSk7CgkJLy9TeXN0ZW0ub3V0LnByaW50bG4oaGlnaEluZGV4KTsKCQlpZihzZWFyY2g+YXJyW2hpZ2hJbmRleF0pewoJCQlTeXN0ZW0ub3V0LnByaW50bG4oLTEpOwoJCQlyZXR1cm47CgkJfQoJCWludCBzID0gLTE7CgkJaWYoaGlnaEluZGV4IT0wJiZhcnJbMF08PXNlYXJjaCl7CgkJCXMgPSBhaS5iUyhhcnIsIDAsIGhpZ2hJbmRleCwgZmFsc2UsIHNlYXJjaCk7CgkJCWlmKHMhPS0xKXsKCQkJCVN5c3RlbS5vdXQucHJpbnRsbihzKTsKCQkJCXJldHVybjsKCQkJfQoJCX0KCQlpZihoaWdoSW5kZXghPWFyci5sZW5ndGgmJmFyclthcnIubGVuZ3RoLTFdPD1zZWFyY2gpewoJCQlzID0gYWkuYlMoYXJyLCBoaWdoSW5kZXgrMSwgYXJyLmxlbmd0aC0xLCB0cnVlLCBzZWFyY2gpOwoJCQlpZihzIT0tMSl7CgkJCQlTeXN0ZW0ub3V0LnByaW50bG4ocyk7CgkJCQlyZXR1cm47CgkJCX0KCQl9CgkJU3lzdGVtLm91dC5wcmludGxuKHMpOwoJfQoJCglwdWJsaWMgaW50IGJTKGludFtdIGEsIGludCBsb3csIGludCBoaWdoLCBib29sZWFuIHJldiwgaW50IHZhbCl7CgkJaWYobG93PmhpZ2gpewoJCQlyZXR1cm4gLTE7CgkJfQoJCWludCBtaWQgPSAobG93K2hpZ2gpLzI7CgkJaWYoYVttaWRdPT12YWwpewoJCQlyZXR1cm4gbWlkOwoJCX0KCQlpZihhW21pZF0+dmFsKXsKCQkJaWYocmV2KXsKCQkJCXJldHVybiBiUyhhLCBtaWQrMSwgaGlnaCwgcmV2LCB2YWwpOwoJCQl9ZWxzZXsKCQkJCXJldHVybiBiUyhhLCBsb3csIG1pZC0xLCByZXYsIHZhbCk7CgkJCX0KCQl9CgkJCgkJaWYocmV2KXsKCQkJcmV0dXJuIGJTKGEsIGxvdywgbWlkLTEsIHJldiwgdmFsKTsKCQl9ZWxzZXsKCQkJcmV0dXJuIGJTKGEsIG1pZCsxLCBoaWdoLCByZXYsIHZhbCk7CgkJfQoJfQoJCglwdWJsaWMgaW50IGhpZ2hlc3RFbGVtKGludFtdIGEsIGludCBsb3csIGludCBoaWdoKXsKCQlpZihsb3c9PWhpZ2gpewoJCQlyZXR1cm4gbG93OwoJCX0KCQlpZihoaWdoLWxvdz09MSl7CgkJCXJldHVybiBhW2xvd10+YVtoaWdoXT9sb3c6aGlnaDsKCQl9CgkJaW50IG1pZCA9IChoaWdoK2xvdykvMjsKCQlpZihhW21pZF08YVttaWQrMV0pewoJCQlyZXR1cm4gaGlnaGVzdEVsZW0oYSwgbWlkKzEsIGhpZ2gpOwoJCX0KCQlpZihhW21pZC0xXT5hW21pZF0pewoJCQlyZXR1cm4gaGlnaGVzdEVsZW0oYSwgbG93LCBtaWQtMSk7CgkJfQoJCXJldHVybiBtaWQ7Cgl9Cn0=