Nihat $1, 2, ... , n$ ədədlərini sıra ilə düzdü, daha sonra isə Hüseyn gəlib bu ədədlərin yerlərini dəyişdirdi. İndi əlimizdə $1$-dən $n$-ə kimi ədədlərdən ibarət qarışıq $p_1, p_2, ..., p_n$ ardıcıllığı var.

Verilmiş ardıcıllıq üçün aşağıdakı cəmi hesablamaq tələb olunur.

$$ \sum_{l = 1}^N \sum_{r = l}^N min(p_l, p_{l+1}, ..., p_r) $$

Daha sadə desək, massivdəki bütün ardıcıl alt-massivlər üçün minimumların cəmini tapın.

min funksiyası daxil olan ədədlərin ən kiçiyini tapır.

\InputFile

İlk sətirdə bir tam ədəd $n$$(1 ≤ n ≤ 10^5)$ – ardıcıllığın elementləri sayı, ikinci sətidə isə $n$ sayda tam ədəd $p_i$$(1 ≤ p_i ≤ n)$ - ardıcıllığın elementləri verilir.

\OutputFile

Verilmiş ardıcıllığa uyğun tələb olunan cəmi çıxışa verin.