Given an array of \(N\) unique integers \(\{a_0, a_1, a_2, ..., a_{N-1}\}\) sorted in non-ascending order (greatest to least), we will use a special binary search algorithm determine the location of an integer \(K\) in the array. Instead of comparing \(K\) with the element in the middle of the array, we will compare it to the element at the index two-thirds from the beginning of the array, rounded down.

For example, in an array of \(5\) elements starting at index \(0\), we compare \(K\) to the element at index \(2\), since \(0 + \lfloor(4 - 0)\times\frac{2}{3}\rfloor = \lfloor4\times\frac{2}{3}\rfloor = \lfloor2.\overline{6}\rfloor = 2\).

Input Specifications

The first line of input will contain \(N\) \((1 \le N \le 100)\).

The second line of input will contain \(N\) space-separated integers, representing each element \(a_i\) \((0 \le a \le 200)\) in the array.

The third line of input will contain \(K\) \((0 \le K \le 200)\).

Output specification

At each step of the search, output the integer that we compare \(K\) to.

Finally output the index \(i\) such that \(a_i = K\), or -1 if no such index exists (meaning the value does not exist in the array).

Sample Input 1

9
11 10 9 7 6 3 2 1 0
5

Sample Output 1

3
9
7
6
-1

Sample Input 2

9
11 10 9 7 6 3 2 1 0
2

Sample Output 2

3
1
2
6