{"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":"\r\n\u003csection\u003e\r\n\u003cp\u003eThere are \u003cvar\u003e\\(N\\)\u003c/var\u003e squares in a row. The squares are numbered \u003cvar\u003e\\(1, 2, ..., N\\)\u003c/var\u003e from left to right.\u003c/p\u003e\r\n\u003cp\u003eYou have two pieces, initially placed on square \u003cvar\u003e\\(A\\)\u003c/var\u003e and \u003cvar\u003e\\(B\\)\u003c/var\u003e, respectively.\r\nYou will be asked to process \u003cvar\u003e\\(Q\\)\u003c/var\u003e queries of the following kind, in the order received:\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eGiven an integer \u003cvar\u003e\\(x_i\\)\u003c/var\u003e, move one of the two pieces of your choice to square \u003cvar\u003e\\(x_i\\)\u003c/var\u003e.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eHere, it takes you one second to move a piece one square.\r\nThat is, the time it takes to move a piece from square \u003cvar\u003e\\(X\\)\u003c/var\u003e to \u003cvar\u003e\\(Y\\)\u003c/var\u003e is \u003cvar\u003e\\(|X-Y|\\)\u003c/var\u003e seconds.\u003c/p\u003e\r\n\u003cp\u003eYour objective is to process all the queries in the shortest possible time.\u003c/p\u003e\r\n\u003cp\u003eYou may only move the pieces in response to queries, and you may not move both pieces at the same time.\r\nAlso, it is not allowed to rearrange the order in which queries are given.\r\nIt is, however, allowed to have both pieces in the same square at the same time.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Constraints","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 ≤ N, Q ≤ 200,000\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 ≤ A, B ≤ N\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 ≤ x_i ≤ N\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Input","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eInput is given from Standard Input in the following format:\u003c/p\u003e\r\n\u003cpre\u003e\u003cvar\u003e\\(N\\)\u003c/var\u003e \u003cvar\u003e\\(Q\\)\u003c/var\u003e \u003cvar\u003e\\(A\\)\u003c/var\u003e \u003cvar\u003e\\(B\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(x_1\\)\u003c/var\u003e \u003cvar\u003e\\(x_2\\)\u003c/var\u003e ... \u003cvar\u003e\\(x_Q\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"Output","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eLet the shortest possible time to process all the queries be \u003cvar\u003e\\(X\\)\u003c/var\u003e seconds. Print \u003cvar\u003e\\(X\\)\u003c/var\u003e.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"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\u003e8 3 1 8\r\n3 5 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003cp\u003eAll the queries can be processed in seven seconds, by:\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003emoving the piece at square \u003cvar\u003e\\(1\\)\u003c/var\u003e to \u003cvar\u003e\\(3\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003emoving the piece at square \u003cvar\u003e\\(8\\)\u003c/var\u003e to \u003cvar\u003e\\(5\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003emoving the piece at square \u003cvar\u003e\\(3\\)\u003c/var\u003e to \u003cvar\u003e\\(1\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"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\u003e9 2 1 9\r\n5 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003cp\u003eThe piece at square \u003cvar\u003e\\(9\\)\u003c/var\u003e should be moved first.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"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\u003e9 2 1 9\r\n5 9\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003cp\u003eThe piece at square \u003cvar\u003e\\(1\\)\u003c/var\u003e should be moved first.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"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\u003e11 16 8 1\r\n1 1 5 1 11 4 5 2 5 3 3 3 5 5 6 7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e21\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\u003c/section\u003e\r\n"}}]}