{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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."},{"iden":"output","content":"For each query count the number of sought pairs of indices (i, j) and print it in a separate line."},{"iden":"examples","content":"Input71 5 2 1 7 2 281 3 4 52 3 5 71 4 3 72 6 4 71 6 2 53 3 6 74 5 1 42 3 4 5Output12566220"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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$$","simple_statement":"Given an array of n integers and q queries, for each query with ranges [l1, r1] and [l2, r2], count how many pairs (i, j) exist such that i is in [l1, r1], j is in [l2, r2], and a[i] == a[j].","has_page_source":false}