시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)25215111765.000%

문제

길이가 $N$인 두 수열 $(p_1, p_2, \ldots, p_N)$, $(q_1, q_2, \dots, q_N)$ 이 주어진다.

이때 다음 값을 구하여라.

$$\sum_{i=1}^{N} {\sum_{j=1}^{N} {\min(|p_i - p_j|, |q_i - q_j|)} }$$

입력

첫째 줄에 수열의 길이 $N$($ 1 \leq N \leq 1\ 000\ 000$) 이 주어진다.

둘째 줄에는 정수 $p_1, p_2, \ldots, p_N$ 이 공백으로 구분되어 주어진다. ($1 \leq p_i \leq 1\ 000\ 000$)

셋째 줄에는 정수 $q_1, q_2, \ldots, q_N$ 이 공백으로 구분되어 주어진다. ($1 \leq q_i \leq 1\ 000\ 000$)

출력

첫째 줄에 문제의 답을 출력한다.

예제 입력 1

3
1 3 2
1 2 3

예제 출력 1

6

예제 입력 2

4
1 1 1000000 1000000
1000000 1000000 1 1

예제 출력 2

7999992
W3sicHJvYmxlbV9pZCI6IjIyODc4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhYzA0XHViMmU4XHVkNTVjIFx1YmIzOFx1YzgxYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZTM4XHVjNzc0XHVhYzAwICROJFx1Yzc3OCBcdWI0NTAgXHVjMjE4XHVjNWY0ICQocF8xLCBwXzIsIFxcbGRvdHMsIHBfTikkLCAkKHFfMSwgcV8yLCBcXGRvdHMsIHFfTikkIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjU0YyBcdWIyZTRcdWM3NGMgXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG5cclxuPHA+JCRcXHN1bV97aT0xfV57Tn0ge1xcc3VtX3tqPTF9XntOfSB7XFxtaW4ofHBfaSAtIHBfanwsIHxxX2kgLSBxX2p8KX0gfSQkPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzQgJE4kKCQgMSBcXGxlcSBOIFxcbGVxIDFcXCAwMDBcXCAwMDAkKSBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCAkcF8xLCBwXzIsIFxcbGRvdHMsIHBfTiQgXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJDEgXFxsZXEgcF9pIFxcbGVxIDFcXCAwMDBcXCAwMDAkKTxcL3A+XHJcblxyXG48cD5cdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCAkcV8xLCBxXzIsIFxcbGRvdHMsIHFfTiQgXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJDEgXFxsZXEgcV9pIFxcbGVxIDFcXCAwMDBcXCAwMDAkKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjODFjXHVjNzU4IFx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjI4NzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTaG9ydCBRdWVzdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+SSBoYXZlIGEgcXVlc3Rpb24sIGNvdWxkIHlvdSBwbGVhc2UgYW5zd2VyIGl0PzxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGdpdmVuIHR3byBzZXF1ZW5jZXMmbmJzcDskKHBfMSwgcF8yLCBcXGxkb3RzLCBwX04pJCwmbmJzcDskKHFfMSwgcV8yLCBcXGRvdHMsIHFfTikkJm5ic3A7b2YgbGVuZ3RoJm5ic3A7JE4kLiBXaGF0IGlzIHRoZSB2YWx1ZSBvZiB0aGlzIHN1bT88XC9wPlxyXG5cclxuPHA+JCRcXHN1bV97aT0xfV57Tn0ge1xcc3VtX3tqPTF9XntOfSB7XFxtaW4ofHBfaSAtIHBfanwsIHxxX2kgLSBxX2p8KX0gfSQkPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbiB0aGUgZmlyc3QgbGluZSwgYSBzaW5nbGUgaW50ZWdlciZuYnNwOyROJCZuYnNwO2lzIGdpdmVuICgkIDEgXFxsZXEgTiBcXGxlcSAxXFwsMDAwXFwsMDAwJCkuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBzZWNvbmQgbGluZSwmbmJzcDskTiQmbmJzcDtpbnRlZ2VycyZuYnNwOyRwXzEsIHBfMiwgXFxsZG90cywgcF9OJCZuYnNwO2FyZSBnaXZlbiAoJDEgXFxsZXEgcF9pIFxcbGVxIDFcXCwwMDBcXCwwMDAkKS48XC9wPlxyXG5cclxuPHA+SW4gdGhlIHRoaXJkIGxpbmUsJm5ic3A7JE4kJm5ic3A7aW50ZWdlcnMmbmJzcDskcV8xLCBxXzIsIFxcbGRvdHMsIHFfTiQmbmJzcDthcmUgZ2l2ZW4gKCQxIFxcbGVxIHFfaSBcXGxlcSAxXFwsMDAwXFwsMDAwJCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGEgc2luZ2xlIGludGVnZXIsIHRoZSBhbnN3ZXIgdG8gdGhlIHF1ZXN0aW9uLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=