Split Sort

You are given a permutation$$$^{\dagger}$$$ $$$p_1, p_2, \ldots, p_n$$$ of integers $$$1$$$ to $$$n$$$.

You can change the current permutation by applying the following operation several (possibly, zero) times:

• choose some $$$x$$$ ($$$2 \le x \le n$$$);
• create a new permutation by:
  • first, writing down all elements of $$$p$$$ that are less than $$$x$$$, without changing their order;
  • second, writing down all elements of $$$p$$$ that are greater than or equal to $$$x$$$, without changing their order;
• replace $$$p$$$ with the newly created permutation.

For example, if the permutation used to be $$$[6, 4, 3, 5, 2, 1]$$$ and you choose $$$x = 4$$$, then you will first write down $$$[3, 2, 1]$$$, then append this with $$$[6, 4, 5]$$$. So the initial permutation will be replaced by $$$[3, 2, 1, 6, 4, 5]$$$.

Find the minimum number of operations you need to achieve $$$p_i = i$$$ for $$$i = 1, 2, \ldots, n$$$. We can show that it is always possible to do so.

$$$^{\dagger}$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).