Given an integer n you need to calculate the number of distinct permutations {1, 2, 3, ..., n} such that the permutation represents a linear max heap.

In other words for each position from 1 to n: p[i] > p[2*i] and p[i] > p[2*i+1]

Example: Input: 4 Output: 3

I need help solving this problem, at least a hint please.