Decision tree complexity of finding parameters of “zigzag” array

Question

I am currently studying for a test on data structures.

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

An array is called a zigzag array if there are $1 \leq i \leq j \leq n$ so that the array increases from $1$ to $i$, decreases from $i$ to $j$, and increases from $j$ to $n$.

Input: a zigzag array. Output: the position of $i$ and $j$.

My answer:

• Upper bound: just going on the array and finding $i$ and $j$, which takes $O(N)$.
• Lower bound: I think that we need to find pairs $i$ and $j$ for which $k$ is bigger than $i$ in $n$ elements, I don't know how to solve it.