Taco Stack Sorting

In this problem, you are given a stack of items, each with an associated expiry period. Your task is to determine the minimum number of "split and merge" operations needed to sort the stack such that the items are arranged in descending order of their expiry periods. A stack is considered sorted if for every adjacent pair of elements, the following condition holds:

(a_i \geq a_{i+1})

If the stack is already sorted, then no operation is needed (0 operations). Otherwise, only one operation is necessary because a single "split and merge" operation allows you to reorganize the stack arbitrarily. You need to handle special cases like an empty stack (M = 0) or a stack with a single item (M = 1), both of which are considered sorted.

Examples:

• Input: 3 items with expiry periods [3, 2, 1] - Output: 0 (already sorted)
• Input: 5 items with expiry periods [4, 3, 2, 5, 1] - Output: 1 (needs reordering)

inputFormat

The first line contains an integer M (the number of items in the stack). The second line contains M space-separated integers representing the expiry periods of the items.

outputFormat

Output a single integer: 0 if the stack is already sorted in descending order, or 1 if at least one split and merge operation is needed to sort it.## sample

3
3 2 1

0