{"raw_statement":[{"iden":"background","content":"距今 300 年前，史前科学文明跨越了界限。出现了凌驾人类的人工智能，也就是超人机械。\n\n不为人知的诞生，等察觉到时，世界已经在【他】的手中了。\n\n究竟他身在何处，有什么样的外貌，虽然直到最后都没有人知道。但他好像可以出现在任何地方，化为任何样貌。\n\n既非敌对，也非压制，单纯只是力量上占上风而已。也不太常出手进行干涉。我想一定是人类对他来说无所谓吧。\n\n但即使如此，他还是会帮人实现愿望，魔人或魔龙，各式各样的不可思议，都是有人追求才被造出来的。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/qmrcnbwc.png)\n\n......\n\n然而在某一天，超人机械消失了。\n\n被腐铁菌干掉了，只是躲了起来，启程前往次元的另一端等，众说纷纭。留下的只有超人机械莫名其妙的发明品。和被世人自己弄得一团乱的世界。\n\n这座树海一定也是超人机械的产物。魔力会一下子增幅，一下子又消耗掉对吧？魔法是从异次元将力量取出的能力，是超出人类理解范围的技术。"},{"iden":"statement","content":"给定一个序列 $a$ ，我们定义一个二元组 $(i,j)$ 为一个逆序对当且仅当 $i<j$ 且 $a_i>a_j$ 。定义两个逆序对 $(i_1,j_1),(i_2,j_2)$ **本质不同** 当且仅当 $a_{i_1}\\ne a_{i_2}$ 或 $a_{j_1}\\ne a_{j_2}$ 。\n\n现在给出 $a$ 序列，问本质不同逆序对个数。\n\n这还不够。\n\n现在有 $q$ 组修改，每一次修改形如 $x~y$ 表示修改 $a_x$ 为 $y$ ，每一次修改 **不互相独立** ，即这一次修改会影响到后面的所有修改。\n\n你需要对于每一次修改输出序列本质不同逆序对个数。\n\n为了体现本题的不同解法，本题不同测试点拥有不同的时空限制。"},{"iden":"input","content":"第一行一个整数 $n$ ，表示序列长度。\n\n第二行 $n$ 个整数 $a_i$ ，表示序列 $a$ 。\n\n第三行一个整数 $q$ ，表示询问组数。\n\n后面 $q$ 行每行两个整数表示一次修改。"},{"iden":"output","content":"一行一个整数，表示初始序列中本质不同逆序对个数。\n\n后面 $q$ 行每行一个整数，第 $i + 1$ 行表示第 $i$ 次修改后序列本质不同逆序对个数。"},{"iden":"note","content":"Idea：DPair，Solution：DPair，Code：DPair，Data：DPair\n\n对于 $100\\%$ 的数据 $1\\le n \\le 10^5, 0\\le q \\le 10^5, 1\\le a_i, x, y \\le n$ 。\n\n以下为子任务：（留空部分表示无特殊限制）\n\n| 测试点编号 | $n$       | $q$       | $a_i,y$ | 特殊性质 | 时空限制 | 对应大样例 |\n| ---------- | --------- | --------- | ------- | -------- | -------- | ---------- |\n| 1-3        | $\\le2000$ | $\\le2000$ |         | A        | 1s/500MB | Sample1    |\n| 4-5        |           | $=0$      |         | A        | 1s/50MB  | Sample2    |\n| 6-10       |           |           |         | A        | 3s/500MB | Sample3    |\n| 11-15      |           |           |         |          | 3s/500MB |            |\n| 16-20      |           |           |         |          | 1s/50MB  |            |\n\n特殊性质 A：保证数据完全随机"}],"translated_statement":null,"sample_group":[["5\n3 1 2 1 5 \n1\n3 3","3\n1"],["6\n1 1 4 5 1 4\n3\n1 5\n1 1\n4 4","3\n3\n3\n1"],["15\n6 14 12 12 6 8 9 3 8 14 14 15 6 15 2 \n10\n12 13\n10 10\n14 9\n8 8\n11 11\n5 8\n1 6\n11 12\n2 13\n1 9","23\n25\n29\n30\n24\n29\n29\n29\n24\n20\n20"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}