Problem A
Pivot
An
A Partition algorithm is an
integral part of a popular sorting algorithm Quicksort. Usually, the choice of pivot is randomized so that Quicksort has an expected
Now the actual job in this problem is this: Starting from an
array A that has
For example, if A’ =
Input
The input consists of two lines. The first line contains
integer
Output
Output the required answer as a single integer in one line.
Sample Input 1 | Sample Output 1 |
---|---|
8 2 1 3 4 7 5 6 8 |
3 |
Sample Input 2 | Sample Output 2 |
---|---|
7 1 2 3 4 5 7 6 |
5 |