Поверхность мира Хайрул усеяна холмами и ущельями, полными опасностей.
Зельда ориентируется по карте Хайрула, на которой отмечено $$$n$$$ локаций. Каждая локация имеет свою высоту над уровнем моря $$$a_i$$$.
Холм — это подпоследовательность локаций (не обязательно идущих подряд, но имеющих возрастающие номера), высоты которых сначала строго возрастают, а затем строго убывают. Иными словами, последовательность $$$i_1, \ldots, i_k$$$ называется холмом, если $$$i_1 < i_2 < \ldots < i_k$$$ и есть некоторое $$$j$$$ от $$$1$$$ до $$$k$$$, что $$$a_{i_1} < a_{i_2} < \ldots < a_{i_j}$$$ и $$$a_{i_j} > a_{i_{j+1}} > \ldots > a_{i_k}$$$. Обратите внимание, что холм может состоять даже из одной локации.
Чтобы спасти Линка и все королевство от неизвестного врага, порождающего порталы в Застывший Мир, необходимо подсчитать количество всех возможных холмов в Хайруле. Казалось бы, это не сильно связанные вещи, но Зельда знает, что делает.
Поскольку холмов может быть очень много, Зельде достаточно найти остаток от деления количества холмов на $$$10^9 + 7$$$. Помогите принцессе справиться с этой задачей.
В первой строке ввода дано целое положительное число $$$n$$$ — число локаций в мире Хайрул ($$$1 \le n \le 10^5$$$).
Во второй строке перечислены $$$n$$$ чисел $$$a_i$$$ — высоты локаций ($$$0 \le a_i \le 10^9$$$).
Выведите одно целое число — остаток от деления общего числа холмов на $$$10^9 + 7$$$.
53 2 5 1 4
20
32 1 3
6