Given an array of size n consisting of n-1 distinct elements.In other words there is exactly one element that is repeated.It is given that the element that would repeat would be either the maximum element or the minimum element. Find the number of structurally different max heaps possible using all the n elements of the array that is max heap of size n.

Let us take an example with array array elements as

1 5 5

The possible max heaps using the given elements are:- First: 5 on the root. 1 as the left child of root and 5 as the right child of the root

5

/ \ 1 5

Second: 5 on the root. 5 as the left child of root and 1 as the right child of the root.

5

/ \ 5 1

second example : N = 6, 1 1 2 3 4 5 ans = 11. N can be upto 1000.

when integers are all different T[N] = (n-1)C(left) * T[L] *T[R] , but what will be the recusion in this case.