Chef and Sorting

Chef has a sequence $A_1, A_2, \ldots, A_N$. He wants to sort it in non-decreasing order. Unfortunately, he can only modify it using specific operations. In each operation, Chef should do the following: - Choose an integer $K$ such that $0 \lt K \lt 2^{30}$. - Choose an integer $P$ such that $1 \leq P \leq N$. - Perform one of the following actions: - type $t = 1$: for each $i$ ($1 \le i \