/* 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. */
import java.util.Scanner;
class Ideone
{
{
Scanner sc
= new Scanner
(System.
in); int t = sc.nextInt();
while(t-- > 0) {
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++) arr[i] = sc.nextInt();
int x = sc.nextInt();
System.
out.
print("arr: ");printArray
(arr
); System.
out.
print("; "+x
+" is at position "+search
(arr, x
));System.
out.
println(); }
}
public static void printArray(int[] arr) {
for(int i
= 0; i
< arr.
length; i
++) System.
out.
print(arr
[i
] + " "); }
public static int search(int[] arr, int x) {
int start = 0, mid = 0, end = arr.length - 1;
while(start <= end) {
mid = (start+end) / 2;
if(x == arr[mid]) return mid;
if(arr[mid] <= arr[end]) {
if(x > arr[mid] && x <= arr[end]) start = mid + 1;
else end = mid - 1;
}
else {
if(x >= arr[start] && x < arr[mid]) end = mid - 1;
else start = mid + 1;
}
}
return -1;
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KaW1wb3J0IGphdmEudXRpbC5TY2FubmVyOwoKY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCVNjYW5uZXIgc2MgPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pOwoJCWludCB0ID0gc2MubmV4dEludCgpOwoJCXdoaWxlKHQtLSA+IDApIHsKCQkJaW50IG4gPSBzYy5uZXh0SW50KCk7CgkJCWludFtdIGFyciA9IG5ldyBpbnRbbl07CgkJCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspIGFycltpXSA9IHNjLm5leHRJbnQoKTsKCQkJaW50IHggPSBzYy5uZXh0SW50KCk7CgkJCVN5c3RlbS5vdXQucHJpbnQoImFycjogIik7cHJpbnRBcnJheShhcnIpOwoJCQlTeXN0ZW0ub3V0LnByaW50KCI7ICIreCsiIGlzIGF0IHBvc2l0aW9uICIrc2VhcmNoKGFyciwgeCkpO1N5c3RlbS5vdXQucHJpbnRsbigpOwoJCX0KCX0KCXB1YmxpYyBzdGF0aWMgdm9pZCBwcmludEFycmF5KGludFtdIGFycikgewoJCWZvcihpbnQgaSA9IDA7IGkgPCBhcnIubGVuZ3RoOyBpKyspIFN5c3RlbS5vdXQucHJpbnQoYXJyW2ldICsgIiAiKTsKCX0KCXB1YmxpYyBzdGF0aWMgaW50IHNlYXJjaChpbnRbXSBhcnIsIGludCB4KSB7CgkJaW50IHN0YXJ0ID0gMCwgbWlkID0gMCwgZW5kID0gYXJyLmxlbmd0aCAtIDE7CgkJd2hpbGUoc3RhcnQgPD0gZW5kKSB7CgkJCW1pZCA9IChzdGFydCtlbmQpIC8gMjsKCQkJaWYoeCA9PSBhcnJbbWlkXSkgcmV0dXJuIG1pZDsKCQkJaWYoYXJyW21pZF0gPD0gYXJyW2VuZF0pIHsKCQkJCWlmKHggPiBhcnJbbWlkXSAmJiB4IDw9IGFycltlbmRdKSBzdGFydCA9IG1pZCArIDE7CgkJCQllbHNlIGVuZCA9IG1pZCAtIDE7CgkJCX0KCQkJZWxzZSB7CgkJCQlpZih4ID49IGFycltzdGFydF0gJiYgeCA8IGFyclttaWRdKSBlbmQgPSBtaWQgLSAxOwoJCQkJZWxzZSBzdGFydCA9IG1pZCArIDE7CgkJCX0KCQl9CgkJcmV0dXJuIC0xOwoJfQp9