Cô giáo Alice muốn cho các con kẹo trong lớp mầm non. Các bạn nhỏ ngồi thành 1 hàng và mỗi bạn nhỏ sẽ có một điểm ưu tiên khi nhận kẹo. Cô Alice muốn đưa cho ít nhất mỗi bạn nhỏ 1 cái kẹo nhưng phải thỏa mãn điều kiện 2 bạn nhỏ ngồi gần nhau thì bạn nhỏ nào có điểm ưu tiên cao hơn sẽ được nhiều kẹo hơn. Cô Alice muốn giảm thiểu tối đa tổng số kẹo sẽ phát cho các bạn nhỏ.

Ví dụ mảng độ ưu tiên khi nhận kẹo của các bạn nhỏ như sau: [4, 6, 4, 5, 6, 2]

Cô Alice có thể phát kẹo theo phương án sau [1, 2, 1, 2, 3, 1]

Ràng buộc:

1 <= n <= 10^5

1 <= a[i] <= 10^5

Input 01:

6
4 6 4 5 6 2

Output 01:

10

Input 02:

8
1 2 8 9 6 5 4 3

Output 02:

21

Giải thích: Số kẹo sẽ chia như sau: 1 2 3 5 4 3 2 1

Cho một xâu kí tự S chỉ bao gồm các chữ cái và chữ số, hãy thực hiện tách các số xuất hiện trong xâu ra và ghép lại với nhau để tạo thành một số tự nhiên lớn nhất. Ví dụ với xâu S = "123abcda234kkf11" thì ta sẽ tách được các số 123, 234 và 11, trong trường hợp các số bắt đầu bằng chữ số 0 thì ta loại bỏ các số 0 vô nghĩa này. Sau đó ghép lại với nhau thành số 23412311 là số lớn nhất có thể đạt được.

Ràng buộc: 1 ≤ len(S) ≤ 100000;

In ra số lớn nhất ghép được.

Input:

123abcda234kkf11

Output:

23412311

Cho một mảng các số nguyên gồm N phần tử. Tìm khoảng cách (độ chênh lệch) nhỏ nhất của 2 phần tử bất kỳ trong mảng.

Ràng buộc: ~1 \leq N \leq 2.10^5~; ~1 \leq A[i] \leq 10^9~

input:

5
1 2 7 5 6

Output:

1