Decision tree complexity of deciding whether array is "zigzag" I am currently studying for a test on data structures.

I have to find the lower and upper bounds for the following problem:


  Input: an array with $n$ numbers. 
  
  Output: boolean answer for the question if there exist $1\le i\le j\le n$ so that:
  
  
  All the elements in the array between $1$ and $i$ are in ascending order.
  All the elements in the array between $i$ and $j$ are in descending order.
  All the elements in the array between $j$ and $n$ are in ascending order. 
  We call this type of array a zigzag array. 
  


I have these ideas: in general, in order to find an upper bound I am looking for an efficient algorithm. For lower bound I am using the decision tree model. For example: in order to find the lower bound for comparison sort algorithms of $n$ numbers, we have $n!$ leaves on the binary decision tree, so we have $n!$ different possibilities for sorting $n$ numbers, which results in an $Ω(n \log n)$ lower bound.

For upper bound I am thinking about just moving from the first element step by step and finding if the array is a zigzag or not, so upper bound is $O(n)$

Lower bond: I don't know how many different possibilities of zigzag arrays of length $n$ we have, so i don't know how so solve it. If one of you has a different method of finding the lower bound I will be happy to know.
You can prove a lower bound of $n-3$ comparisons, almost matching the trivial upper bound of $n-1$ comparisons (surely the gap can be closed with a bit more work). The proof uses an adversary argument. Whenever the algorithm compares two elements $s&lt;t$, the answer is always $A[s]&lt;A[t]$ unless $s=n-1$ and $t=n$, in which case the answer is $A[n-1]&gt;A[n]$.

It is always consistent that the array is zigzag, with $i=n-1$ and $j=n$ (the order is $A[1] &lt; A[2] &lt; \cdots &lt; A[n-2] &lt; A[n] &lt; A[n-1]$). Now suppose you make less than $n-3$ comparisons. In particular, if you think of your comparisons as edges on the graph on vertices $\{1,\ldots,n-2\}$ (we ignore comparisons to $A[n-1]$ or $A[n]$), then the graph is disconnected. In particular, there are vertices $s&lt;t \leq n-2$ which weren't compared. It is therefore consistent that $A[s] &gt; A[t]$ whereas $A[t] &lt; A[n-1] &gt; A[n]$ (for example, the order could be $A[1] &lt; \cdots &lt; A[s-1] &lt; A[t] &lt; A[s] &lt; \cdots &lt; A[n-2] &lt; A[n] &lt; A[n-1]$), in which case the array isn't zigzag since it has two disjoint decreasing parts. Hence the algorithm doesn't know the answer.