Given an array of integers arr = [5, 6, 1]. When we construct a BST with this input in the same order, we will have "5" as root, "6" as the right child and "1" as left child.

Now if our input is changed to [5,1,6], our BST structure will still be identical.

So given an array of integers, how to find the number of different permutations of the input array that results in the identical BST as the BST formed on the original array order?