Binary Search on Sorted Array

You are given a sorted array of n integers in non-decreasing order. Your task is to implement a binary search algorithm to determine the index of a given target value within the array. If the target exists in the array, output its index (using 0-indexing); otherwise, output -1.

The binary search algorithm operates by repeatedly dividing the search interval in half. Begin with the entire array, and if the target value is less than the value in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Continue this process until the target is found or the interval is empty.

This problem requires you to read input from stdin and write the result to stdout.

Note: The input format guarantees that the array is sorted. If the target occurs multiple times, any valid occurrence index is acceptable.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. An integer n representing the number of elements in the array.
2. A line with n space-separated integers in non-decreasing order.
3. An integer target representing the value to search for.

outputFormat

Output a single integer to standard output (stdout): the index of the target value in the array if found; otherwise, output -1.

## sample

5
1 2 3 4 5
3

2

</p>