Choose Two Equal Subsets

Problem Statement

Choose Two Equal Subsets You are given an array A consisting of N distinct integers. For each index i , find the number of ways you can choose two subsets of the same size such that: The first subset is from the numbers that are on the left of index i . The second subset is from the numbers that are on the right of index i . Additionally, if we put these two subsets and the number in index i into a new array B and then sort B , the number that was in the index i should be in the middle of B . Find the number of all ways to choose these two subsets. Input Format The first line contains an integer, N , denoting the number of elements in A . Each line i of the N subsequent lines (where 0 ≤ i < N ) contains an integer describing A[i] . Output Format Print a single integer denoting the total number of ways to choose the two subsets. Constraints 1 ≤ N ≤ 10^3 1 ≤ A[i] ≤ 10^9 Examples Input: [Sample input not provided] Output: [Sample output not provided] [Explanation if any, not provided i