{"raw_statement":[{"iden":"problem statement","content":"You are given a permutation $P=(P_1,\\ldots,P_N)$ of $(1,\\ldots,N)$, and an integer $K$.\nFind the number of pairs of integers $(L, R)$ that satisfy all of the following conditions:\n\n*   $1 \\leq L \\leq R \\leq N$\n    \n*   $\\mathrm{max}(P_L,\\ldots,P_R) - \\mathrm{min}(P_L,\\ldots,P_R) \\leq R - L + K$"},{"iden":"constraints","content":"*   $1 \\leq N \\leq 1.4\\times 10^5$\n*   $P$ is a permutation of $(1,\\ldots,N)$.\n*   $0 \\leq K \\leq 3$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$\n$P_1$ $P_2$ $\\ldots$ $P_N$"},{"iden":"sample input 1","content":"4 1\n1 4 2 3"},{"iden":"sample output 1","content":"9\n\nThe following nine pairs $(L, R)$ satisfy the conditions.\n\n*   $(1,1)$\n*   $(1,3)$\n*   $(1,4)$\n*   $(2,2)$\n*   $(2,3)$\n*   $(2,4)$\n*   $(3,3)$\n*   $(3,4)$\n*   $(4,4)$\n\nFor $(L,R) = (1,2)$, we have $\\mathrm{max}(A_1,A_2) -\\mathrm{min}(A_1,A_2) = 4-1 = 3$ and $R-L+K=2-1+1 = 2$, not satisfying the condition."},{"iden":"sample input 2","content":"2 0\n2 1"},{"iden":"sample output 2","content":"3"},{"iden":"sample input 3","content":"10 3\n3 7 10 1 9 5 4 8 6 2"},{"iden":"sample output 3","content":"37"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}