Pretty Graph

Chef was recently given an array $A$ (size $N$) with distinct elements, he really loves graphs, so he decided to build a graph with $N$ nodes out of the array as follows - For each $i$, $j$, nodes $i$ and $j$ are connected if $i$< $j$ and $A_i \ge A_j$ He noticed that the resulting graph was very complicated and not pretty, so he decided to remove some of the vertices from the graph. If a vertex