{"problem":{"name":"Ex - Beautiful Subsequences","description":{"content":"You are given a permutation $P=(P_1,\\ldots,P_N)$ of $(1,\\ldots,N)$, and an integer $K$. Find the number of pairs of integers $(L, R)$ that satisfy all of the following conditions: *   $1 \\leq L \\leq ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc248_h"},"statements":[{"statement_type":"Markdown","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$\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$P_1$ $P_2$ $\\ldots$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc248_h","tags":[],"sample_group":[["4 1\n1 4 2 3","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."],["2 0\n2 1","3"],["10 3\n3 7 10 1 9 5 4 8 6 2","37"]],"created_at":"2026-03-03 11:01:13"}}