Let \(C_0\) and \(C_N\) be the numbers of buildings visible from the left and right ends, respectively.

The Cartesian Tree of the sequence of building heights \(H\) (with the maximum of each interval as the root of the corresponding subtree) determines \(C\). Conversely, let us consider reconstructing the Cartesian Tree from \(C\).

A sequence of \(k\) buildings gives a sequence of length \(k+1\) representing the numbers of buildings visible from its \(k+1\) “gaps.” Suppose we start with an empty sequence, insert the buildings in descending order of height, and record the sequence of visible-building counts at the gaps after each insertion. Consider reversing this process. Focus on the shortest building. The numbers of buildings visible from immediately to its left and immediately to its right are equal. Let this number be \(x\). When this building is removed, the number of buildings visible from the resulting gap becomes \(x-1\).

It follows that the necessary and sufficient condition for reconstructing a Cartesian Tree from \(C=(C_0,C_1,\dots, C_{N})\) is as follows.

• It is possible to obtain \(C=(0)\) by repeatedly performing the following operation on \(C\).
  • Let \(x\) be the maximum value in \(C\). Find the leftmost adjacent pair of occurrences of \(x\), remove those two occurrences of \(x\) from the sequence, and insert \(x-1\) in their place.

This construction itself gives the Cartesian Tree. In an implementation, we do not need to explicitly merge maximum values: we can scan \(C\) from the beginning and process it with a stack. Also, for a given Cartesian Tree \(T\), consider the number of sequences \(H\) that produce this tree as their Cartesian Tree. For each vertex \(v\) of \(T\), let \(S_v\) be the size of the subtree rooted at \(v\). It is known that this number of sequences is

\[ \dfrac{N!}{\prod_{v}S_v} \]

We have now solved the problem when \(C_0\) and \(C_N\) are also given. Be careful about cases where no Cartesian Tree can be reconstructed: the answer is \(0\) in such cases.

In fact, we can narrow down the candidates for \(C_0,C_N\) to at most two possibilities. The operations used to reconstruct the Cartesian Tree have the invariant \(\sum_{x\in C}2^{-x}=1\). Thus, when \(1-\sum_{i=1}^{N-1}2^{-C_i}\) is written in binary, we only need to check two candidates if it has two set bits, or one candidate if it has one set bit. Pay attention to whether \(C_0=C_N\) holds. We may obtain two different Cartesian Trees.

This algorithm runs in \(O(N)\) time.