/* 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
{
{
// your code goes here
}
private static boolean binarySearch(int[] ar, int searchItem) {
int i = 1;
int lower = 0;
int upper = ar.length - 1;
int mid;
while (true) {
mid = (lower + upper) / 2;
if (ar[mid] == searchItem)
i++;
//return true;
else
if (lower > upper)
i++;
//return false;
else
if (searchItem > ar[mid])
lower = mid + 1;
else
upper = mid - 1;
}
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCX0KCQoJcHJpdmF0ZSBzdGF0aWMgYm9vbGVhbiBiaW5hcnlTZWFyY2goaW50W10gYXIsIGludCBzZWFyY2hJdGVtKSB7CiAgICAgICAgICAgICAgICBpbnQgaSA9IDE7CiAgICAgICAgICAgICAgICBpbnQgbG93ZXIgPSAwOwogICAgICAgICAgICAgICAgaW50IHVwcGVyID0gYXIubGVuZ3RoIC0gMTsKICAgICAgICAgICAgICAgIGludCBtaWQ7CiAKICAgICAgICAgICAgICAgIHdoaWxlICh0cnVlKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIG1pZCA9IChsb3dlciArIHVwcGVyKSAvIDI7CiAKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGFyW21pZF0gPT0gc2VhcmNoSXRlbSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpKys7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLy9yZXR1cm4gdHJ1ZTsKICAgICAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIChsb3dlciA+IHVwcGVyKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGkrKzsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC8vcmV0dXJuIGZhbHNlOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIChzZWFyY2hJdGVtID4gYXJbbWlkXSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbG93ZXIgPSBtaWQgKyAxOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB1cHBlciA9IG1pZCAtIDE7CiAgICAgICAgICAgICAgICB9CiAKICAgICAgICB9Cn0=