Айбар солдан оңға қарай \(1\)-ден \(n\)-ға дейін нөмірленген \(n\) карта үйлерін қатар тұрғызды. \(i\)-ші үйдің беріктігі \(a_i\)-ға тең.

Енді Айбар барлық үйлерді қиратпақшы. Ол үшін бірінші үйдің сол жағына желдеткішті орналастырады. Ол желдеткіш \(X\) бүтін санына тең күшпен үйлерге қарай жел соғады. Егер \(i\)-ші үйдің беріктігі \(X\)-тан аз болса, онда ол келесі үйге құлап, оның беріктігін \(a_i\)-ға азайтады. Келесі үйдің беріктігі \(a_i\)-дан аз болса, онда оның беріктігі \(0\)-ге тең болады. Жел барлық үйлерді бір-бірден солдан оңға қарай соғады. Үй құласа, ол келесі үйдің беріктігін жел соққанға дейін азайтады. Барлық үйлердің құлауы үшін желдің ең аз күшін табыңыз.

Тапсырманы жақсырақ түсіну үшін ескертуді қараңыз.

Input

Бірінші жолда бір бүтін \(n\) саны \((1 \le n \le 10^6)\) — үйлер саны берілген.

Екінші жолда \(n\) бүтін сандар \(a_1\), \(a_2\), \(\dots\), \(a_n\) \((1 \le a_i \le 10^9)\) — үйлердің беріктіктері берілген.

Output

Бір бүтін санды басып шығарыңыз — барлық үйлер құлауы үшін желдің ең аз күші.

Sample Input 1

5
2 5 1 3 6

Sample Output 1

4

Notes

Мысалда жел күші \(4\) болады.

Бірінші үйдің беріктігі \(2\)-ге тең. Ол екінші үйге құлайды және екінші үйдің беріктігі \(5-2=3\) тең болады. Екінші үй үшінші үйге құлайды, ал үшінші үйдің беріктігі \(0\)-ге тең болады. Үшінші үй төртіншіге құлайды, ал төртінші үйдің беріктігі \(3-0=3\) тең болады. Төртінші үй бесіншіге құлайды және бесінші үйдің беріктігі \(6-3=3\) тең болады. Бесінші үйдің беріктігі желдің күшінен аз, сондықтан құлап қалады.

Жел күші одан аз болса, барлық үйлер құламайтынын көрсетуге болады.