{"trustable":true,"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":"HTML","content":"\u003cp\u003eAlice đang chơi một trò chơi với người bạn thân thiện của cô, Marisa.\u003c/p\u003e\u003cp\u003eCó $$$n$$$ hộp được sắp xếp thành một dãy, được đánh số bằng các số nguyên từ $$$1$$$ đến $$$n$$$ từ trái sang phải. Marisa sẽ giấu một con búp bê trong một trong những hộp. Sau đó, Alice sẽ có $$$m$$$ cơ hội đoán xem con búp bê ở đâu. Nếu Alice đoán đúng số hộp, nơi con búp bê đang ở, cô sẽ thắng trò chơi, nếu không, người bạn của cô sẽ thắng trò chơi.\u003c/p\u003e\u003cp\u003eĐể thắng, Marisa sẽ sử dụng một số chiêu trò không công bằng. Sau mỗi lần Alice đoán một hộp, cô có thể di chuyển con búp bê đến hộp kế cận hoặc giữ nó ở chỗ. Các hộp $$$i$$$ và $$$i + 1$$$ là kế cận cho tất cả $$$1 \\leq i \\leq n - 1$$$. Cô cũng có thể sử dụng chiêu trò này một lần trước khi trò chơi bắt đầu.\u003c/p\u003e\u003cp\u003eVì vậy, trò chơi diễn ra theo thứ tự sau: trò chơi bắt đầu, Marisa thực hiện chiêu trò, Alice đoán lần đầu tiên, Marisa thực hiện chiêu trò, Alice đoán lần thứ hai, Marisa thực hiện chiêu trò, $$$\\ldots$$$, Alice đoán lần thứ $$$m$$$, Marisa thực hiện chiêu trò, trò chơi kết thúc.\u003c/p\u003e\u003cp\u003eAlice đã nghĩ ra một chuỗi $$$a_1, a_2, \\ldots, a_m$$$. Trong lần đoán thứ $$$i$$$, cô sẽ hỏi xem con búp bê có ở trong hộp $$$a_i$$$ không. Cô muốn biết số lượng kịch bản $$$(x, y)$$$ (cho tất cả $$$1 \\leq x, y \\leq n$$$), sao cho Marisa có thể thắng trò chơi nếu cô đặt con búp bê vào hộp thứ $$$x$$$ ban đầu và cuối cùng của trò chơi, con búp bê sẽ ở trong hộp thứ $$$y$$$. Hãy giúp cô và tính toán số lượng này.\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa hai số nguyên $$$n$$$ và $$$m$$$, được phân tách bằng dấu cách ($$$1 \\leq n, m \\leq 10^5$$$)\u0026nbsp;— số lượng hộp và số lần đoán, mà Alice sẽ thực hiện.\u003c/p\u003e\u003cp\u003eDòng tiếp theo chứa $$$m$$$ số nguyên $$$a_1, a_2, \\ldots, a_m$$$, được phân tách bằng dấu cách ($$$1 \\leq a_i \\leq n$$$), số $$$a_i$$$ đại diện cho số hộp mà Alice sẽ đoán trong lần thứ $$$i$$$.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eIn ra số lượng kịch bản trong một dòng, hoặc số lượng cặp hộp $$$(x, y)$$$ ($$$1 \\leq x, y \\leq n$$$), sao cho nếu Marisa đặt con búp bê vào hộp có số $$$x$$$, cô có thể sử dụng chiêu trò một cách sao cho cuối cùng của trò chơi, con búp bê sẽ ở trong hộp có số $$$y$$$ và cô sẽ thắng trò chơi.\u003c/p\u003e"}},{"title":"Ví dụ","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\u003e3 3\n2 2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"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\u003e5 2\n3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e21\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eTrong ví dụ đầu tiên, các kịch bản có thể là $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(3, 2)$$$, $$$(3, 3)$$$.\u003c/p\u003e\u003cp\u003eHãy lấy $$$(2, 2)$$$ làm ví dụ. Các hộp, mà con búp bê sẽ ở trong suốt trò chơi có thể là $$$2 \\to 3 \\to 3 \\to 3 \\to 2$$$\u003c/p\u003e"}}]}