Zach had no luck finding patterns in his sequence of numbers after they were sorted according to the last digit. He decided to go back to regular ascending order, but needs help finding the index of certain numbers in the sequence, if they even exist. He is under a lot of time pressure and needs a fast solution that runs in O(log n) or better.

Input

The first line contains a number ~a\ (0 \leq x_i \leq 10^9)~, the number Zach is looking for in the sequence.

The second line contains an integer ~n\ (1 \leq n \leq 10^6)~ representing the amount of numbers in the sequence.

The next line consists of ~n~ unique space separated integers ~x_i\ (0 \leq x_i \leq 10^9)~ which form the sequence.

Output

Output the index of the number ~a~ in the sequence (0-indexed) if it exists. Otherwise output -1.

Example

Input 1

7
5
1 3 7 8 9

Output 1

2

Explanation 1

1 has an index of 0, 3 has an index of 1, 7 has an index of 2, and so on. The output is the index of 7, which is 2.

Input 2

6
5
1 3 7 8 9

Output 2

-1

Explanation 2

6 is not in the sequence.