{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIn the game \u0027Goose Goose Duck\u0027, the geese\u0027s target is to complete the tasks and stay alive. However the saboteurs, ducks, will try to stop the geese from completing the tasks by killing them.\u003c/p\u003e\u003cp\u003eNow consider a game consisting of $$$n$$$ geese and $$$k$$$ ducks. The geese are numbered from $$$1$$$ to $$$n$$$, and the $$$i$$$-th goose can complete the task numbered $$$a_i$$$. The geese decided to dispatch an interval of geese to complete the task, which means they will choose two integers $$$\\ell$$$ and $$$r$$$, satisfying $$$1\\leq \\ell\\leq r\\leq n$$$, and all geese numbered $$$i$$$ which satisfy that $$$\\ell\\leq i\\leq r$$$ will go to complete their task. Such a decision is called a plan, two plans are considered different if and only if the interval is different.\u003c/p\u003e\u003cp\u003eDifferent tasks have different locations. The ducks will crouch at a task location, and kill all the geese trying to complete the task at this location. They can not choose a task location where more than $$$k$$$ geese will come, because they can\u0027t kill them all and there will be witnesses, they also can not choose a task location where less than $$$k$$$ geese will come, because they will kill their teammates by mistake. In other words, they can only choose a task location where exactly $$$k$$$ geese will come. \u003c/p\u003e\u003cp\u003eA plan is said to be dangerous if and only if there exists a task location that the ducks can ambush. Please help the geese to count how many plans are \u003cspan class\u003d\"tex-font-style-bf\"\u003enot dangerous\u003c/span\u003e for the geese. Please notice that the geese do not have to complete all the tasks with the plan.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers $$$n$$$ and $$$k$$$ ($$$1\\leq n,k\\leq 10^6$$$).\u003c/p\u003e\u003cp\u003eThe second line contains $$$n$$$ integers, the $$$i$$$-th integer $$$a_i$$$ ($$$1\\leq a_i\\leq 10^6$$$) denotes the task number of the goose numbered $$$i$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput one line containing one integer, denoting the answer.\u003c/p\u003e"}},{"title":"Examples","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\u003e6 2\n1 2 2 1 3 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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\u003e6 1\n1 2 3 4 5 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}