Мін-Макс-Множення!#485

Мін-Макс-Множення!

1 секунда
256 мегабайтів
Дуже складна

Містер IP знайшов цілий масив довжини . Він вільний на вихідних, тому знайшов собі заняття:

Для кожного підмасиву (1 \le l \le r \le n) визначте

\operatorname{mn}(l,r) = \min(a_l, a_{l+1}, \dots, a_r),
\operatorname{mx}(l, r) = \max(a_l, a_{l+1}, \dots, a_r).

Тепер його цікавить значення

S = \sum_{l=1}^{n} \sum_{r=l}^{n} \operatorname{mn}(l, r) \cdot \operatorname{mx}(l, r).

Оскільки воно може бути дуже великим, він хоче знати лише його залишок при діленні на 10^9 + 7 (іншими словами, S \mod (10^9 + 7)). Допоможіть йому обчислити це!

Вхідні дані

Перший рядок містить єдине ціле число (1 \le n \le 5 \cdot 10^5) — довжина масиву.

Другий рядок містить цілих чисел a_1, a_2, \dots, a_n (1 \le a_i \le 10^6).

Вихідні дані

Виведіть єдине ціле число — значення залишку за модулем 10^9 + 7.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

У першому прикладі всі підмасиви та їх внески:

  • : \min = 1, \max = 1, внесок 1 \cdot 1 = 1

  • : \min = 1, \max = 2, внесок 1 \cdot 2 = 2

  • [1,2,3]: \min = 1, \max = 3, внесок 1 \cdot 3 = 3

  • : \min = 2, \max = 2, внесок 2 \cdot 2 = 4

  • : \min = 2, \max = 3, внесок 2 \cdot 3 = 6

  • : \min = 3, \max = 3, внесок 3 \cdot 3 = 9

Сума всіх внесків дорівнює 1 + 2 + 3 + 4 + 6 + 9 = 25.

Оцінювання

У кожному блоці тести оцінюються незалежно.

  1. ( балів): n \leq 2000;

  2. ( балів): a_i \leq a_{i+1} для всіх 1 \leq i \leq n-1;

  3. ( балів): серед елементів не більше різних значень;

  4. ( балів): n \leq 10^5;

  5. ( балів): без додаткових обмежень.