Binary Search in a Sorted Array

You are given a sorted array of integers and a target integer. Your task is to implement the binary search algorithm to find the index of the target value in the array. If the target is not present in the array, output -1.

The binary search algorithm divides the search interval in half repeatedly until the target is found or the interval is empty. The formula used to calculate the middle index is given by \( mid = left + \lfloor (right - left) / 2 \rfloor \).

Ensure that your solution reads the input from stdin and outputs the result to stdout.

inputFormat

The input consists of three parts provided via standard input:

1. The first line contains an integer \( n \) representing the number of elements in the array.
2. The second line contains \( n \) space-separated integers in sorted order.
3. The third line contains an integer \( target \) representing the value to be searched.

outputFormat

Output a single integer, which is the index of the target in the array if found; otherwise, output -1.

## sample

10
1 2 3 4 5 6 7 8 9 10
3

2

</p>