-dən -ə qədər olan ədədlərin permutasiyası üçün funksiyasını aşağıdakı kimi təyin edək: 1 \le i \le j \le n olmaqla hər bir cütü üçün cütünə baxaq, burada — p_i, p_{i+1}, \ldots, p_j ədədlərinin ən kiçiyi, isə ən böyüyüdür. Onda bütün \frac{n(n+1)}{2} cüt arasındakı müxtəlif cütlərin sayına bərabərdir.
Məsələn, (1, 3, 2) permutasiyasına baxaq.
cütü üçün (min, max) = (1, 1)
cütü üçün (min, max) = (1, 3)
cütü üçün (min, max) = (1, 3)
cütü üçün (min, max) = (3, 3)
cütü üçün (min, max) = (2, 3)
cütü üçün (min, max) = (2, 2)
Ümumilikdə müxtəlif cüt var, buna görə də f((1, 3, 2)) = 5.
Verilmiş (p_1, p_2, \ldots, p_n) permutasiyası üçün qiymətini tapın.
Birinci sətirdə bir tam ədəd (1 \le n \le 2\cdot 10^5) verilir.
İkinci sətirdə tam ədəd p_1, p_2, \ldots, p_n (1 \le p_i \le n, bütün p_i cüt-cüt müxtəlifdir) — uzunluğu olan permutasiya verilir.
qiymətini çap edin.
Nümunə 1
Nümunə 2
Nümunə 3
Birinci nümunə məsələnin şərtində izah olunub.