Question
QuickSort Pivot Candidates
You are given an array arr consisting of n distinct positive integers.
This array represents the result of several partition operations performed during a QuickSort-like process on some original array.
During QuickSort, each chosen pivot ensures that all values to its left are smaller and all values to its right are greater.
Your task is to determine how many elements in the given array could legitimately have served as pivots at some stage of this process, ultimately producing the final arrangement arr.
Input
The first line contains an integer n - the size of the array.
The next line contains n distinct space separated integers arr1, arr2, arr3, .... ., arrn - the elements of the array.
The next line contains n distinct space separated integers arr1, arr2, arr3, .... ., arrn - the elements of the array.
Output
Print a single integer: The number of elements in arr that could have acted as valid pivots during the partition steps.
Example
Input
8
6 1 4 7 13 10 17 19
Output
3
Explanation
The values 7, 17, and 19 satisfy the pivot property:
Every element to the left is smaller, and every element to the right is larger. Thus, they are valid pivot candidates.
8
6 1 4 7 13 10 17 19
Output
3
Explanation
The values 7, 17, and 19 satisfy the pivot property:
Every element to the left is smaller, and every element to the right is larger. Thus, they are valid pivot candidates.