{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"Ying 一直在和她的朋友聊天。她有 n 个朋友,从 1 到 n 编号。\n她最近的聊天列表可以用大小为 n 的排列 p 来表示。p\u003csub\u003e1\u003c/sub\u003e 是 Ying 最近联系的朋友,p\u003csub\u003e2\u003c/sub\u003e 是第二个最近的朋友,依此类推。\n最初, Ying 的最近聊天列表 p 为 1, 2, ..., n(即一个顺序排列)。\n之后她收到 m 条消息,第 j 条消息来自朋友 a\u003csub\u003ej\u003c/sub\u003e 。这会导致朋友 a\u003csub\u003ej\u003c/sub\u003e 移动到排列中的第一个位置,其他人则依次往后退。不过若 a\u003csub\u003ej\u003c/sub\u003e 已经在第一个位置,则不需要任何操作。\n\n例如,若最近的聊天列表为 p \u003d [4, 1, 5, 3, 2] ;\n\n如果她收到朋友 3 的消息,则 p 变为 [3, 4, 1, 5, 2] ;\n如果她收到朋友 4 的消息,那么 p 不会改变 [4, 1, 5, 3, 2] ;\n如果她收到朋友 2 的消息,则 p 变为 [2, 4, 1, 5, 3] 。\n\n现在Ying依次收到了m条消息,她想知道,在这个过程中,每一个朋友,最靠前排在第几位,最靠后排在第几位。"}},{"title":"Input","value":{"format":"MD","content":"第一行包含两个整数 n 和 m ( 1 ≤ n, m ≤ 3 × 10\u003csup\u003e5\u003c/sup\u003e )——分别是 Ying 的朋友数和收到的消息数。\n\n第二行包含 m 个整数 a\u003csub\u003e1\u003c/sub\u003e, a\u003csub\u003e2\u003c/sub\u003e, ..., a\u003csub\u003em\u003c/sub\u003e ( 1 ≤ a\u003csub\u003ei\u003c/sub\u003e ≤ n )——分别表示Ying接收到了来自a\u003csub\u003ei\u003c/sub\u003e的消息。 "}},{"title":"Output","value":{"format":"MD","content":"输出包含 n 对整数。 对于每个朋友输出他在接受m条消息的过程中最小位置和最大位置。 "}},{"title":"Examples","value":{"format":"MD","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e5 4\n3 5 1 4\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e1 3\n2 5\n1 4\n1 5\n1 5\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e4 3\n1 2 4\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e1 3\n1 2\n3 4\n1 4\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"MD","content":"\n在第一个示例中, Ying 的最近聊天列表如下所示\n[1, 2, 3, 4, 5] \n[3, 1, 2, 4, 5] \n[5, 3, 1, 2, 4] \n[1, 5, 3, 2, 4] \n[4, 1, 5, 3, 2] \n很容易看出来,对于朋友1,最靠前在第1位,最靠后为第3位。\n同理,朋友2的最小位置和最大位置分别为(2, 5)\n朋友3的最小位置和最大位置分别为(1, 4)\n朋友4的最小位置和最大位置分别为(1, 5)\n朋友5的最小位置和最大位置分别为(1, 5)"}}]}