Sadə cəm#9004

Sadə cəm

1 saniyə
128 meqabayt
Asan

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ə -də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.

Giriş

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

Çıxış

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

Nümunələr

Nümunə 1

Loading
Loading

Nümunə 2

Loading
Loading