问题陈述
给你两个序列 A=(A_1,\ldots,A_N) 和 B=(B_1,\ldots,B_N) 长度 N.
定义一个序列 C 作为以空序列开始并附加得到的序列 A_i 副本 B_i,结果长度为 \sum_{i=1}^N A_i.
求倒数 C.
什么是反转数?
序列的反转数 C = (C_1, C_2, \dots, C_M) 定义为索引对的数量 (i, j) 这样 1 \leq i < j \leq M 和 C_i > C_j.约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^3
- 1 \leq B_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
输出
打印答案。
示例输入 1
3 4 1 2 10 30 20
示例输出 1
2
序列 C is (10,10,10,10,30,20,20),其反转数为 2.
示例输入 2
4 1000 1000 1000 1000 1 1 1 1
示例输出 2
0
的反转数 C is 0.
示例输入 3
13 3 1 4 1 5 9 2 6 5 3 5 8 9 2 7 1 8 2 8 1 7 2 7 4 5 9
示例输出 3
499