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.

https://www.hackerrank.com/contests/world-codesprint-6/challenges/beautiful-3-set

I can't quite understand how to solve the problem. Although there is an editorial it's really poorly written as it only explains how to get an upperbound for the number of sets but it doesn't explain why that upperbound is achievable and how to come up with a formula for the numbers that satisfy the bound.

Thanks in advance.