{"problem":{"name":"[Ynoi1999] XM66F","description":{"content":"给定序列 $a_1,\\dots,a_n$ ，$m$ 次询问，每次询问给出 $l,r$ ，问有多少组 $(i,j,k)$ 满足 $l\\le i<j<k\\le r,\\;a_i=a_k>a_j$ 。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10149"},"statements":[{"statement_type":"Markdown","content":"给定序列 $a_1,\\dots,a_n$ ，$m$ 次询问，每次询问给出 $l,r$ ，问有多少组 $(i,j,k)$ 满足 $l\\le i<j<k\\le r,\\;a_i=a_k>a_j$ 。\n\n## Input\n\n第一行两个整数 $n,m$。\n\n第二行 $n$ 个整数 $a_1,\\dots,a_n$。\n\n接下来 $m$ 行每行两个整数 $l,r$ 表示一个询问。\n\n## Output\n\n共 $m$ 行，每行一个整数，依次表示每个询问的答案。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/f05zotfr.png)\n\n## Note\n\nIdea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078\n\n所有数值为整数。\n\n对于 $100\\%$ 的数据，满足 $1\\le a_i\\le n$，$1\\le l\\le r\\le n$，$n,m\\le 5\\times 10^5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10149","tags":["1999","O2优化","Ynoi"],"sample_group":[["10 5\n9 8 5 4 5 1 5 1 5 8\n2 8\n4 9\n7 9\n6 7\n2 3","4\n4\n1\n0\n0"]],"created_at":"2026-03-03 11:09:25"}}