농부 존의 N (1≤N≤5⋅10^5) 마리의 소들이 일렬로 서 있으며, 소 1번이 줄의 맨 앞에, 소 N번이 줄의 맨 뒤에 있다. 농부 존의 소들은 여러 다른 종(species)으로 이루어져 있다. 그는 각 종을 1부터 N까지의 정수로 표시한다. 줄의 앞에서 i번째에 있는 소의 종은 a_i(1≤a_i≤N)다.

농부 존은 소들을 지역 소 병원에서 검진받게 하려 한다. 하지만 소 수의사는 매우 까다로워서, 줄의 i번째 소를 검진하려면 반드시 그 소가 종 b_i (1≤b_i≤N)이어야 한다.

농부 존은 게을러서 소들의 순서를 완전히 재배열하고 싶지 않다. 대신 그는 다음과 같은 연산을 딱 한 번 수행할 것이다.

두 정수 l과 r을 선택하여(1≤l≤r≤N), 줄의 l번째부터 r번째까지의 소들의 순서를 반대로 뒤집는다.

농부 존은 이 방법이 얼마나 효과적인지 측정하고 싶다.

가능한 모든 \frac{N\cdot(N+1)}2개의 연산에 대해, 검진받는 소들의 수의 합을 구하시오.

#8258 upload 11 done 5 how_to_reg 5 call_split Subtarea

소 병원 검진 timer 1s memory 1024MB

#8258
Subtarea

소 병원 검진 1s 1024MB