Корови Фермера Джона мають висоти \(1, 2, \ldots, N\). Якось вишикувалися в ряд в деякому порядку для гри у фрісбі. Нехай \(h_1 \ldots h_N\) позначають висоти цих корів у заданому порядку (тому \(h\)'-ки є перестановка чисел \(1 \ldots N\)).

Дві корови на позиціях \(i\) і \(j\) у рядку можуть успішно кинути фрісбі один одному, якщо і тільки якщо всі корови між ними мають ріст менше, ніж \( min (h_i, h_j) \).

Обчисліть суму відстаней між усіма парами позицій \(i<j\), які обмежені парою корів, які можуть успішно кидати фрісбі один одному. Відстань між позиціями \(i\) та \(j\) є \(j-i+1\).

Формат вхідних даних

Перший рядок введення містить одне ціле число \(N\). Наступний рядок уведення містить \(h_1 \ldots h_N\), розділені одиночними пробілами. (\(1 \le N \le 3*10^5\))

Формат вихідних даних

Виведіть суму відстаней для всіх пар позицій, в яких корови можуть кинути фрісбі один одному.

Для відповіді використовуйте 64-бітове ціле (наприклад, "long long" C/C++).

Приклад вхідних даних

7
4 3 1 2 5 6 7

Приклад вихідних даних

24

Пари відповідних позицій для цього прикладу:

(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5), (5, 6), (6 , 7)

ОЦІНЮВАННЯ

• У тестах 1-3 N≤5000.
• У тестах 4-11 немає додаткових обмежень.

Автор: Quanquan Liu