Counting Frequency in a Sorted Array

You are given a sorted array of integers (in non-decreasing order) and a target integer x. Your task is to determine how many times x appears in the array.

Using efficient algorithms of binary search, you should compute the frequency of x by finding its first and last occurrences. Recall that in a sorted array, binary search can locate the bounds in logarithmic time.

The formula to compute the frequency is given by:

$$\text{frequency} = \text{upper_bound}(x) - \text{lower_bound}(x) $$

where \(\text{lower_bound}(x)\) returns the first index at which x could be inserted without disturbing the order, and \(\text{upper_bound}(x)\) returns the first index beyond the last occurrence of x.

inputFormat

The input is read from stdin and consists of three parts:

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 which form the sorted array.
3. The third line contains a single integer x, the target value whose frequency needs to be counted.

outputFormat

Output the frequency of x in the array to stdout as a single integer.

## sample

7
1 2 2 2 3 4 5
2

3