Sorting Prefixes

You are given an array $A$, which is a permutation of the integers $[1, N]$. Your task is to sort the array using the following operations as many times as you want: - Choose an index $i$ ($1 \le i \le N$), and then pay $A_i$ coins to sort the prefix $A[1, i]$ of the array. (Note that the cost is levied before the sorting operation is performed) Here, $A[1, i]$ represents the prefix $[A_1, A_2