{"problem":{"name":"D. Strange Queries","description":{"content":"You are given an array with n integers a1, a2, ..., an, and q queries to answer. Each query consists of four integers l1, r1, l2 and r2. Your task is to count the number of pairs of indices (i, j) sa","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10113D"},"statements":[{"statement_type":"Markdown","content":"You are given an array with n integers a1, a2, ..., an, and q queries to answer.\n\nEach query consists of four integers l1, r1, l2 and r2. Your task is to count the number of pairs of indices (i, j) satisfying the following conditions:\n\nThe first line of the input contains an integer n (1 ≤ n ≤ 50 000) — the size of the given array.\n\nThe second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n).\n\nThe third line contains an integer q (1 ≤ q ≤ 50 000) — the number of queries.\n\nEach of the next q lines contains four integers l1, r1, l2, r2 (1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n), describing one query.\n\nFor each query count the number of sought pairs of indices (i, j) and print it in a separate line.\n\n## Input\n\nThe first line of the input contains an integer n (1 ≤ n ≤ 50 000) — the size of the given array.The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n).The third line contains an integer q (1 ≤ q ≤ 50 000) — the number of queries.Each of the next q lines contains four integers l1, r1, l2, r2 (1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n), describing one query.\n\n## Output\n\nFor each query count the number of sought pairs of indices (i, j) and print it in a separate line.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the size of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ a_i \\in \\{1, 2, \\dots, n\\} $.  \nLet $ q \\in \\mathbb{Z}^+ $ be the number of queries.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 50{,}000 $  \n2. $ 1 \\leq a_i \\leq n $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\leq q \\leq 50{,}000 $  \n4. For each query $ k \\in \\{1, \\dots, q\\} $:  \n   - $ 1 \\leq l_{1,k} \\leq r_{1,k} \\leq n $  \n   - $ 1 \\leq l_{2,k} \\leq r_{2,k} \\leq n $  \n\n**Objective**  \nFor each query $ k $, compute:  \n$$\nC_k = \\left| \\left\\{ (i, j) \\mid i \\in [l_{1,k}, r_{1,k}],\\ j \\in [l_{2,k}, r_{2,k}],\\ a_i = a_j \\right\\} \\right|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10113D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}