{"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 صديق مات 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"}}]}