{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Problem Statement","value":{"format":"HTML","content":"\u003csection\u003e\nTakahashi has grown up and decided to live alone away from his parents. He wants to move the cardboard boxes from the truck to his new room, but if the floor of the room is filled with cardboard boxes, he won\u0027t be able to lay out his futon to sleep today.\u003cbr\u003e\nTherefore, instead of spreading out the boxes one by one, he decided to make a stack of cardboard boxes to a certain extent. However, the cardboard boxes have a specific weight, and if a heavier box is stacked on top of a lighter box, the box at the bottom will be crushed.\u003cbr\u003e\n\u003cdiv class\u003d\"img-caption\"\u003e\n\t\u003cimg src\u003d\"CDN_BASE_URL/43933ae7f21f8881740ddef89bd24c5a?v\u003d1710484957\" width\u003d\"300\" height\u003d\"187\"\u003e\n\t\u003cdiv class\u003d\"caption\"\u003eFigure: The cardboard at the bottom must be heavier than the one on top\u003c/div\u003e\n\u003c/div\u003e\n\n\u003cbr\u003e\nThe weights of the cardboard boxes are given in the order they are carried from the truck. Think of a way to stack the boxes without crushing them. Then, find the minimum number of stacks of boxes when the boxes are stacked in a way that the box on top is the same weight or lighter than the one below.\n\u003c/section\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003csection\u003e\nThe input is given in the following format and is provided from the standard input.\n\u003cpre\u003e\r\n\u003cvar\u003e\\(N\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(w_1\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(w_2\\)\u003c/var\u003e\r\n:\r\n:\r\n\u003cvar\u003e\\(w_N\\)\u003c/var\u003e\r\n\u003c/pre\u003e\n\u003cul\u003e\n\t\u003cli\u003eThere are \u003cvar\u003e\\(N+1\\)\u003c/var\u003e lines of input.\u003c/li\u003e\n\t\u003cli\u003eOn the \u003cvar\u003e\\(1\\)\u003c/var\u003eth line, an integer \u003cvar\u003e\\(N(1≦N≦50)\\)\u003c/var\u003e representing the number of cardboard boxes is given.\u003c/li\u003e\n\t\u003cli\u003eFrom the \u003cvar\u003e\\(2\\)\u003c/var\u003eth line onwards, \u003cvar\u003e\\(N\\)\u003c/var\u003e lines contain an integer \u003cvar\u003e\\(w_i(1≦w_i≦100,000)\\)\u003c/var\u003e representing the weight of the cardboard box to be carried on the \u003cvar\u003e\\(i\\)\u003c/var\u003eth line.\n\u003c/li\u003e\u003c/ul\u003e\n\u003c/section\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003csection\u003e\nCarry the cardboard boxes in order and output the minimum number of stacks of boxes that can be made where the box on top is the same weight or lighter than the one below to the standard output in \u003cvar\u003e\\(1\\)\u003c/var\u003e line(s).\u003cbr\u003e\nAdditionally, remember to output a newline at the end.\n\u003c/section\u003e"}},{"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\u003e\r\n5\r\n4\r\n3\r\n1\r\n2\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003csection\u003e\n\n\u003c/section\u003e\n\n\u003csection\u003e\n\n\u003cul\u003e\n\u003cli\u003eStacking in the order shown in the figure below results in \u003cvar\u003e\\(2\\)\u003c/var\u003e stacks of cardboard boxes.\u003c/li\u003e\n\u003cli\u003eIt is not possible to stack a cardboard box with weight \u003cvar\u003e\\(2\\)\u003c/var\u003e on top of the \u003cvar\u003e\\(3\\)\u003c/var\u003eth box, so it cannot be made into \u003cvar\u003e\\(1\\)\u003c/var\u003e stacks, making the minimum \u003cvar\u003e\\(2\\)\u003c/var\u003e.\n\u003c/li\u003e\u003c/ul\u003e\n\u003cdiv class\u003d\"img-nocaption\"\u003e\n\t\u003cimg src\u003d\"CDN_BASE_URL/bba2f0bd3809b044e07f8228fecbdfd3?v\u003d1710484957\" width\u003d\"800\" height\u003d\"156\"\u003e\n\u003c/div\u003e\n\u003c/section\u003e"}},{"title":"Sample 2","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\u003e\r\n7\r\n93\r\n249\r\n150\r\n958\r\n442\r\n391\r\n25\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003csection\u003e\n\n\u003c/section\u003e\n\n\u003csection\u003e\n\n\u003cul\u003e\n\u003cli\u003eStacking in the shape shown below results in \u003cvar\u003e\\(3\\)\u003c/var\u003e stacks of boxes.\u003c/li\u003e\n\u003cdiv class\u003d\"todo\"\u003eCorrection: The 225 cardboard box in the figure is a mistake, it should be 25. Apologies for the error.\u003c/div\u003e\n\u003c/ul\u003e\n\u003cdiv class\u003d\"img-nocaption\"\u003e\n\t\u003cimg src\u003d\"CDN_BASE_URL/4c2f398f99b599a6fdd1a101b066114d?v\u003d1710484957\" width\u003d\"300\" height\u003d\"259\"\u003e\n\u003c/div\u003e\n\u003c/section\u003e"}},{"title":"Sample 3","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\u003e\r\n4\r\n100\r\n100\r\n100\r\n100\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003csection\u003e\n\n\u003c/section\u003e\n\n\u003csection\u003e\n\n\u003cul\u003e\n\u003cli\u003eSince cardboard boxes of the same weight can be stacked, it can be made into \u003cvar\u003e\\(1\\)\u003c/var\u003e stacks of boxes.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/section\u003e"}},{"title":"Sample 4","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\u003e\r\n6\r\n5\r\n10\r\n15\r\n20\r\n25\r\n30\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003csection\u003e\n\n\u003c/section\u003e\n\n\u003csection\u003e\n\n\u003cul\u003e\n\u003cli\u003eSince no cardboard box can be stacked on top of the previously carried box, it is not possible to stack any of them, resulting in \u003cvar\u003e\\(1\\)\u003c/var\u003e stacks being the minimum.\u003c/li\u003e\n\u003cli\u003eTherefore, \u003cvar\u003e\\(6\\)\u003c/var\u003e stacks is the minimum number of stacks.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/section\u003e"}},{"title":"Sample 5","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\u003e\r\n15\r\n3\r\n1\r\n4\r\n1\r\n5\r\n9\r\n2\r\n6\r\n5\r\n3\r\n5\r\n8\r\n9\r\n7\r\n9\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003csection\u003e\n\n\u003c/section\u003e\n\n\u003csection\u003e\n\n\u003cul\u003e\n\u003cli\u003eStacking as shown below results in the minimum number of stacks.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cdiv class\u003d\"img-nocaption\"\u003e\n\t\u003cimg src\u003d\"CDN_BASE_URL/7138e19866f60cb9c857eeabd4a8d121?v\u003d1710484957\" width\u003d\"500\" height\u003d\"168\"\u003e\n\u003c/div\u003e\n\u003c/section\u003e"}}]}