PermütasyoN#12853

PermütasyoN

1 saniye
256 megabayt
Çok zor

'den 'ye kadar olan sayıların bir permütasyonu için fonksiyonunu şu şekilde tanımlayalım: 1 \le i \le j \le n olacak şekildeki her çifti için çiftini ele alalım; burada , p_i, p_{i+1}, \ldots, p_j sayılarının en küçüğü, ise en büyüğüdür. O hâlde , tüm \frac{n(n+1)}{2} çift arasındaki farklı çiftlerin sayısına eşittir.

Örneğin, (1, 3, 2) permütasyonunu ele alalım.

Toplamda farklı çift vardır, dolayısıyla f((1, 3, 2)) = 5.

Verilen (p_1, p_2, \ldots, p_n) permütasyonu için değerini bulun.

Giriş

İlk satırda bir tam sayı (1 \le n \le 2\cdot 10^5) verilir.

İkinci satırda tam sayı p_1, p_2, \ldots, p_n (1 \le p_i \le n, tüm p_i değerleri ikişer ikişer farklıdır) — uzunluğu olan permütasyon verilir.

Çıktı

değerini yazdırın.

Örnekler

Örnek 1

Loading
Loading

Örnek 2

Loading
Loading

Örnek 3

Loading
Loading

Not

İlk örnek problem metninde açıklanmıştır.