Cho một mảng a gồm n phần tử ~a_1~, ~a_2~, ...~a_n~. Trong một bước bạn có thể tăng giá trị của một phần tử bất kỳ trong mảng lên 1 đơn vị. Bạn hãy tính số bước ít nhất để tạo ra mảng a gồm các phần tử tăng dần.

Mảng a tăng dần là mảng có các phần tử ~a_1~ ≤ ~a_2~ ≤ ... ≤ ~a_n~

Input

Gồm 2 dòng:

Dòng thứ nhất là một số nguyên n.(1 ≤ ~n ≤ 10^5~)

Dòng thứ hai là dãy số ~a_1~, ~a_2~, ...~a_n~ cách nhau bởi dấu cách. (1 ≤ ~a_i~ ≤ ~10^9~)

Output

Một dòng duy nhất là

Examples

Input

6
3 1 5 4 8 9 

Output

3 

*Note: *chúng ra tăng phần tử thứ 2 lên 2 đơn vị, phần tử thứ 4 lên 1 đơn vị.