Farmer John의 소 N마리 (1 ≤ N ≤ 7500)는 일렬로 서 있다. 맨 앞에 있는 소는 1번 소, 맨 뒤에 있는 소는 N번 소이다. FJ의 소들은 여러 종(Species)으로 이루어져 있으며, 각 소의 종은 1부터 N까지의 정수로 표현된다. i번째 소의 종을 a_i라고 할 때, 주어진 배열 a = [a_1, a_2, ..., a_N]은 소들의 초기 배치를 나타낸다.

FJ는 소들을 가축 병원(bovine hospital)으로 데려가야 한다. 그런데 수의사는 매우 까다로워서, i번째 소가 검사받으려면 그 소의 종이 b_i여야 한다. 즉, 주어진 배열 b = [b_1, b_2, ..., b_N]은 각 위치에서 검사받아야 할 소의 종을 나타낸다.

FJ는 소들을 완전히 재정렬하는 것을 싫어한다. 그래서 다음과 같은 한 번의 연산만 수행할 수 있다.

두 개의 정수 (l, r)를 선택한다. 구간 [l, r]에 해당하는 소들의 순서를 뒤집는다. 즉, 소들의 위치를 l번부터 r번까지 반전시킨다.

이 작업을 통해 b와 최대한 많은 소들의 종이 일치하도록 만들려고 한다.

FJ는 이 방법이 얼마나 효과적인지 측정하고 싶어 한다. 따라서 c = 0부터 N까지, c마리의 소가 검사받을 수 있도록 만드는 (l, r) 선택 방법의 개수를 구하는 프로그램을 작성하라.

두 연산 (l₁, r₁)과 (l₂, r₂)가 다르다는 것은 다음과 같다.

l₁ ≠ l₂ 또는 r₁ ≠ r₂이면 서로 다른 연산이다.

#8257 upload 4 done 3 how_to_reg 3 call_split Subtask

Cow Checkups timer 1s memory 1024MB

#8257
Subtask

Cow Checkups 1s 1024MB