{"trustable":true,"sections":[{"title":"Description","value":{"format":"MD","content":"给你一个长度为 $n$ 的排列 $p_1,p_2, \\cdots ,p_n$。你需要把它排序。\n\n每次可以花区间长度,即 $r-l+1$ 的代价,选择排列中的任意一段区间 $[l,r]$,并将 $[l,r]$ 从小到大排序。\n\n现在你可以让他进行若干次这个操作,直到 $p$ 中元素的值从 $1$ 到 $n$ 按升序排序,即对于 $1$ 到 $n$ 的每一个 $i$,都有 $p_i\u003di$。\n\n求问花的代价最少为多少?"}},{"title":"Input","value":{"format":"MD","content":"本题有多组询问,第一行有一个数 $T$ 表示询问组数。\n\n对于每组询问:\n\n第一行给出一个整数 $n$。\n\n第二行 $n$ 个整数,由空格隔开,代表排列 $p$ 中元素的值。"}},{"title":"Output","value":{"format":"MD","content":"$T$ 行,每行一个整数表示一组询问的答案。"}},{"title":"Sample 1","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\n3\n1 3 2\n4\n3 2 1 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"MD","content":"【样例 $1$ 说明】\n\n对于第一组数据,可选择区间 $[2,3]$ 进行排序。\n\n对于第二组数据,可选择区间 $[1,3]$ 进行排序。\n\n【数据规模与约定】\n\n对于 $20\\%$ 的数据,$n\\leq 4$。\n\n对于另 $30\\%$ 的数据,$\\sum n\\leq5000$。\n\n对于另 $10\\%$ 的数据,$p_1\u003dn$。\n\n对于 $100\\%$ 的数据,$1\\le T,\\sum n\\le 10^6$。"}}]}