Dövri Sürüşmələr

Giriş

Birinci sətirdə bir tam ədəd $n$ verilir ( $1 \leq n \leq 5000$ 1 \leq n \leq 5000) — permutasiyaların uzunluğu.

İkinci sətirdə $n$ cüt-cüt fərqli tam ədəd $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$ permutasiyası.

Üçüncü sətirdə $n$ cüt-cüt fərqli tam ədəd $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$ permutasiyası.

Çıxış

Bir tam ədəd çap edin — elə minimum ümumi əməliyyat sayı ki, $1$ -dən $n$ -ə qədər hər bir $k$ üçün $a$ permutasiyasının ilk $k$ elementinin cəmi $b$ permutasiyasının ilk $k$ elementinin cəmindən kiçik olmasın.

Nümunələr

Nümunə 1

Loading

Nümunə 2

Loading

Qeyd

Birinci nümunədə şərt artıq heç bir əməliyyat olmadan ödənir, buna görə cavab $0$ -dır.

İkinci nümunədə $a$ permutasiyasını iki dəfə, $b$ permutasiyasını isə bir dəfə dövri sürüşdürə bilərsiniz:

[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$ permutasiyasının prefiks cəmləri $3, 7, 8, 10$ 3, 7, 8, 10, $b$ permutasiyasının prefiks cəmləri isə $2, 6, 7, 10$ 2, 6, 7, 10 olur. Beləliklə, tələb olunan bütün bərabərsizliklər ödənir.

Bunu $3$ -dən az əməliyyatla əldə etmək mümkün deyil, ona görə cavab $3$ -dür.

Bal hesablama

Alt tapşırıq $1$ ( $25$ xal): $n \leq 8$ n \le 8.
Alt tapşırıq $2$ ( $50$ xal): $n \leq 100$ n \le 100.
Alt tapşırıq $3$ ( $85$ xal): $n \leq 1000$ n \le 1000.
Alt tapşırıq $4$ ( $140$ xal): Əlavə məhdudiyyət yoxdur.