Given an array of \(N\) integers \(\{a_0, a_1, a_2, ..., a_{N-1}\}\) sorted in non-ascending order (greatest to least), find the first or last occurrence of an integer \(K\) in the array.

Input Specification

The first line of input will contain \(N\) \((1 \le N \le 10^6)\).

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

The third line of input will contain \(K\) \((0 \le K \le \frac{N}{2})\).

The final line of input will be either first or last, indicating whether to output the first or last occurrence of \(K\).

Output Specification

If the last line of input contains first, output one integer, the least possible index \(i\), such that \(a_i = K\).

Otherwise, if the last line is last, output one integer, the greatest possible index \(i\), such that \(a_i = K\).

Output -1 if no such index exists.

Sample Input 1

9
9 6 6 5 5 5 3 3 2
5
first

Sample Output 1

3

Sample Input 2

9
9 6 6 5 5 5 3 3 2
10
last

Sample Output 2

-1