Please help me answer this simple coding question for an online judge platform. You can write the code in either Python3 or Java8 ; whichever one is easier and faster. Please also provide screenshots of your output after entering the inputs; it should match the sample inputs and outputs in the question. Thank You!

I had posted this before, but got a completely wrong answer. Please provide the correct code that gives the correct output.

An O(n) Partition algorithm partitions an array A around a pivot element (pivot is a member of A) into three parts: a left sub-array that contains elements that are pivot, the pivot itself, and a right sub-array that contains elements that are > pivot. 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 O(n log n) running time performance. Now the actual job in this problem is this: Starting from an array A that has n distinct integers, we partition A using one of the member of A as pivot to produce a transformed array A'. Given this transformed array A', your job is to count how many integers that could have been the chosen pivot. For example, if A -2,1,3, 4,7,5,6,8], then 3 integers: 13,4,8] could have been the pivot of partition, e.g. [2,1,3} to the left of integer 4 are smaller than 4 and {7,5,6,8) to the right of integer 4 are greater than 4 However, the other 5 integers cannot possibly be the pivot, e.g. integer 7 cannot possibly be the pivot as there are 15,6) to the right of integer 7 Input The input consists of two lines. The first line contains integer n (3n distinct 32-bit signed integers that describes the transformed array A 100000). The second line contains n Output Output the required answer as a single integer in one line