Döngüsel Kaydırmalar

Giriş

İlk satırda bir tam sayı $n$ verilir ( $1 \leq n \leq 5000$ 1 \leq n \leq 5000) — permütasyonların uzunluğu.

İkinci satırda ikişer ikişer farklı $n$ tam sayı $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n verilir ( $1 \leq a_{i} \leq n$ 1 \leq a_i \leq n) — $a$ permütasyonu.

Üçüncü satırda ikişer ikişer farklı $n$ tam sayı $b_{1}, b_{2}, \dots, b_{n}$ b_1, b_2, \ldots, b_n verilir ( $1 \leq b_{i} \leq n$ 1 \leq b_i \leq n) — $b$ permütasyonu.

Çıktı

Bir tam sayı yazdırın — $1$ 'den $n$ 'e kadar her $k$ için $a$ permütasyonunun ilk $k$ elemanının toplamının, $b$ permütasyonunun ilk $k$ elemanının toplamından küçük olmaması için gereken en az toplam işlem sayısı.

Örnekler

Örnek 1

Loading

Örnek 2

Loading

Not

Birinci örnekte koşul hiçbir işlem yapılmadan zaten sağlanmaktadır, bu yüzden cevap $0$ 'dır.

İkinci örnekte $a$ permütasyonunu iki kez, $b$ permütasyonunu ise bir kez döngüsel olarak kaydırabilirsiniz:

[1, 2, 3, 4] \to [3, 4, 1, 2],

[1, 2, 3, 4] \rightarrow [3, 4, 1, 2],

[3, 2, 4, 1] \to [2, 4, 1, 3] .

[3, 2, 4, 1] \rightarrow [2, 4, 1, 3].

Bundan sonra $a$ permütasyonunun önek toplamları $3, 7, 8, 10$ 3, 7, 8, 10, $b$ permütasyonunun önek toplamları ise $2, 6, 7, 10$ 2, 6, 7, 10 olur. Böylece gerekli tüm eşitsizlikler sağlanır.

Bunu $3$ 'ten az işlemle elde etmek mümkün değildir, bu yüzden cevap $3$ 'tür.

Puanlama

Alt görev $1$ ( $25$ puan): $n \leq 8$ n \le 8.
Alt görev $2$ ( $50$ puan): $n \leq 100$ n \le 100.
Alt görev $3$ ( $85$ puan): $n \leq 1000$ n \le 1000.
Alt görev $4$ ( $140$ puan): Ek kısıt yoktur.