Size 'den 'ye kadar olan sayıların bir (p_1, p_2, \ldots, p_n) permütasyonu veriliyor.
Bu permütasyon üzerinde aşağıdaki işlemi yapabilirsiniz:
'nin komşu iki elemanının yerini değiştirebilirsiniz. Bu işlem tam olarak bir saniye sürer.
Bir iterasyonda şunları yaparsınız:
Leksikografik sıralamada (p_1, p_2, \ldots, p_n) permütasyonundan hemen önce gelen (q_1, q_2, \ldots, q_n) permütasyonunu göz önüne alın; yani , 'den leksikografik olarak küçüktür ve "aralarında" başka bir permütasyon yoktur. Örneğin, p = (2, 3, 1) için q = (2, 1, 3), p = (3, 1, 2, 4) için q = (2, 4, 3, 1) ve p = (1, 4, 2, 3) için q = (1, 3, 4, 2) olur.
permütasyonunu mümkün olan en az sayıda işlemle permütasyonuna dönüştürün. Örneğin, (1, 4, 2, 3) permütasyonunu (1, 3, 4, 2) permütasyonuna dönüştürmek için en az işlem gerekir: (1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2).
Bu iterasyonu, elde edilen permütasyonuna, o birim permütasyon olana (yani (1, 2, 3, \ldots, n)) eşit olana) kadar uygularsınız. Bu ne kadar zaman alacak? Bu sayı çok büyük olabileceğinden, onu 10^9+7 modunda yazdırın.
Bir permütasyonu, öyle bir indisi varsa ki tüm j<i için p_j = q_j ve ayrıca p_i<q_i olsun, permütasyonundan leksikografik olarak küçük kabul edilir.
Birinci satırda bir tam sayı (1 \le n \le 2\cdot 10^5) — permütasyonun uzunluğu verilir.
İkinci satırda tam sayı p_1, p_2, \ldots, p_n (1 \le p_i \le n, tüm sayılar ikişer ikişer farklıdır) — permütasyonun elemanları verilir.
Süreç sona erene kadar geçecek saniye sayısını 10^9+7 modunda yazdırın.
Örnek 1
Örnek 2
Birinci örnekte elimizde şunlar var:
(1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2): saniye.
(1, 3, 4, 2) \to (1, 3, 2, 4): saniye.
(1, 3, 2, 4) \to (1, 2, 3, 4) \to (1, 2, 4, 3): saniye.
(1, 2, 4, 3) \to (1, 2, 3, 4): saniye.
Toplamda saniye.