{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e Matt的朋友K.Bro是一名ACMer。\u003cbr\u003e\u003cbr\u003e 昨天,K.Bro学习了一个算法:冒泡排序。冒泡排序会比较相邻的两个元素,如果它们的顺序不对就交换它们的位置。这个过程会一直重复,直到不再需要交换为止。\u003cbr\u003e\u003cbr\u003e 今天,K.Bro想出了一个新的算法,并将其命名为K.Bro排序。\u003cbr\u003e\u003cbr\u003e K.Bro排序中有许多轮次。对于每一轮,K.Bro会选择一个数字,并在这个数字比它后面的数字小的情况下不断地与后面的数字交换位置。例如,如果序列是“1 4 3 2 5”,而K.Bro选择了“4”,那么经过这一轮之后,他会得到“1 3 2 4 5”。K.Bro排序类似于冒泡排序,但它是一种随机化的算法,因为K.Bro会在每一轮开始时选择一个随机数。K.Bro想知道,对于给定的序列,在最佳情况下需要多少轮次才能将这个序列排序。换句话说,你需要回答将序列排序为升序所需的最小轮次。为了简化问题,K.Bro承诺序列是1, 2, . . . , N的一个排列。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行只包含一个整数T(T ≤ 200),表示测试用例的数量。对于每个测试用例,第一行包含一个整数N(1 ≤ N ≤ 10\u003csup\u003e6\u003c/sup\u003e)。\u003cbr\u003e\u003cbr\u003e 第二行包含N个整数a\u003csub\u003ei\u003c/sub\u003e(1 ≤ a\u003csub\u003ei\u003c/sub\u003e ≤ N),表示K.Bro给出的序列。\u003cbr\u003e\u003cbr\u003e 所有测试用例中N的总和不会超过3 × 10\u003csup\u003e6\u003c/sup\u003e。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一行“Case #x: y”,其中x是案例编号(从1开始),y是将序列排序所需的最小轮次。"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n5\r\n5 4 3 2 1\r\n5\r\n5 1 2 3 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 4\r\nCase #2: 1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"在第二个样例中,我们选择“5”,这样在第一轮之后,序列变成“1 2 3 4 5”,算法完成。\u003cbr\u003e"}}]}