{"problem":{"name":"D. Inversion Counting","description":{"content":"A permutation of size _n_ is an array of size _n_ such that each integer from 1 to _n_ occurs exactly once in this array. An inversion in a permutation _p_ is a pair of indices (_i_, _j_) such that _i","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF911D"},"statements":[{"statement_type":"Markdown","content":"A permutation of size _n_ is an array of size _n_ such that each integer from 1 to _n_ occurs exactly once in this array. An inversion in a permutation _p_ is a pair of indices (_i_, _j_) such that _i_ > _j_ and _a__i_ < _a__j_. For example, a permutation \\[4, 1, 3, 2\\] contains 4 inversions: (2, 1), (3, 1), (4, 1), (4, 3).\n\nYou are given a permutation _a_ of size _n_ and _m_ queries to it. Each query is represented by two indices _l_ and _r_ denoting that you have to reverse the segment \\[_l_, _r_\\] of the permutation. For example, if _a_ = \\[1, 2, 3, 4\\] and a query _l_ = 2, _r_ = 4 is applied, then the resulting permutation is \\[1, 4, 3, 2\\].\n\nAfter each query you have to determine whether the number of inversions is odd or even.\n\n## Input\n\nThe first line contains one integer _n_ (1 ≤ _n_ ≤ 1500) — the size of the permutation.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ _n_) — the elements of the permutation. These integers are pairwise distinct.\n\nThe third line contains one integer _m_ (1 ≤ _m_ ≤ 2·105) — the number of queries to process.\n\nThen _m_ lines follow, _i_\\-th line containing two integers _l__i_, _r__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ _n_) denoting that _i_\\-th query is to reverse a segment \\[_l__i_, _r__i_\\] of the permutation. All queries are performed one after another.\n\n## Output\n\nPrint _m_ lines. _i_\\-th of them must be equal to _odd_ if the number of inversions in the permutation after _i_\\-th query is odd, and _even_ otherwise.\n\n[samples]\n\n## Note\n\nThe first example:\n\n1.  after the first query _a_ = \\[2, 1, 3\\], inversion: (2, 1);\n2.  after the second query _a_ = \\[2, 3, 1\\], inversions: (3, 1), (3, 2).\n\nThe second example:\n\n1.  _a_ = \\[1, 2, 4, 3\\], inversion: (4, 3);\n2.  _a_ = \\[3, 4, 2, 1\\], inversions: (3, 1), (4, 1), (3, 2), (4, 2), (4, 3);\n3.  _a_ = \\[1, 2, 4, 3\\], inversion: (4, 3);\n4.  _a_ = \\[1, 4, 2, 3\\], inversions: (3, 2), (4, 2).","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"大小为 #cf_span[n] 的排列是一个长度为 #cf_span[n] 的数组，其中每个从 #cf_span[1] 到 #cf_span[n] 的整数恰好出现一次。排列 #cf_span[p] 中的一个逆序对是一对下标 #cf_span[(i, j)]，满足 #cf_span[i > j] 且 #cf_span[ai < aj]。例如，排列 #cf_span[[4, 1, 3, 2]] 包含 #cf_span[4] 个逆序对：#cf_span[(2, 1)]、#cf_span[(3, 1)]、#cf_span[(4, 1)]、#cf_span[(4, 3)]。\n\n给你一个大小为 #cf_span[n] 的排列 #cf_span[a] 和 #cf_span[m] 个对其的查询。每个查询由两个下标 #cf_span[l] 和 #cf_span[r] 表示，表示你需要将排列的区间 #cf_span[[l, r]] 反转。例如，若 #cf_span[a = [1, 2, 3, 4]] 且查询为 #cf_span[l = 2]、#cf_span[r = 4]，则得到的排列为 #cf_span[[1, 4, 3, 2]]。\n\n每次查询后，你需要判断逆序对的数量是奇数还是偶数。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1500]) —— 排列的大小。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[1 ≤ ai ≤ n]) —— 排列的元素。这些整数两两不同。\n\n第三行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 2·105]) —— 需要处理的查询数量。\n\n接下来 #cf_span[m] 行，第 #cf_span[i] 行包含两个整数 #cf_span[li], #cf_span[ri] (#cf_span[1 ≤ li ≤ ri ≤ n])，表示第 #cf_span[i] 个查询是将排列的区间 #cf_span[[li, ri]] 反转。所有查询依次执行。\n\n请输出 #cf_span[m] 行。第 #cf_span[i] 行应为 _odd_（若第 #cf_span[i] 次查询后排列的逆序对数量为奇数），否则为 _even_。\n\n第一个例子：\n\n第二个例子：\n\n## Input\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 1500]) —— 排列的大小。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[1 ≤ ai ≤ n]) —— 排列的元素。这些整数两两不同。第三行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 2·105]) —— 需要处理的查询数量。接下来 #cf_span[m] 行，第 #cf_span[i] 行包含两个整数 #cf_span[li], #cf_span[ri] (#cf_span[1 ≤ li ≤ ri ≤ n])，表示第 #cf_span[i] 个查询是将排列的区间 #cf_span[[li, ri]] 反转。所有查询依次执行。\n\n## Output\n\n请输出 #cf_span[m] 行。第 #cf_span[i] 行应为 _odd_（若第 #cf_span[i] 次查询后排列的逆序对数量为奇数），否则为 _even_。\n\n[samples]\n\n## Note\n\n第一个例子：第一次查询后 #cf_span[a = [2, 1, 3]]，逆序对：#cf_span[(2, 1)]；第二次查询后 #cf_span[a = [2, 3, 1]]，逆序对：#cf_span[(3, 1)]、#cf_span[(3, 2)]。第二个例子：#cf_span[a = [1, 2, 4, 3]]，逆序对：#cf_span[(4, 3)]；#cf_span[a = [3, 4, 2, 1]]，逆序对：#cf_span[(3, 1)]、#cf_span[(4, 1)]、#cf_span[(3, 2)]、#cf_span[(4, 2)]、#cf_span[(4, 3)]；#cf_span[a = [1, 2, 4, 3]]，逆序对：#cf_span[(4, 3)]；#cf_span[a = [1, 4, 2, 3]]，逆序对：#cf_span[(3, 2)]、#cf_span[(4, 2)]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the size of the permutation.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $.  \nAn **inversion** is a pair $ (i, j) $ such that $ i < j $ and $ a_i > a_j $.  \nLet $ I(A) $ denote the total number of inversions in $ A $.  \n\nLet $ m \\in \\mathbb{Z}^+ $ be the number of queries.  \nEach query is a pair $ (l, r) $ with $ 1 \\leq l \\leq r \\leq n $, representing the reversal of the subarray $ A[l:r] $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 1500 $  \n2. $ 1 \\leq m \\leq 2 \\cdot 10^5 $  \n3. $ 1 \\leq a_i \\leq n $, all $ a_i $ distinct  \n4. $ 1 \\leq l \\leq r \\leq n $ for each query  \n\n**Objective**  \nAfter each query, determine the parity of $ I(A) $, i.e., output **odd** if $ I(A) \\mod 2 = 1 $, **even** if $ I(A) \\mod 2 = 0 $.  \n\nThe reversal of segment $ [l, r] $ updates $ A $, and the parity of inversions must be recomputed efficiently after each update.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF911D","tags":["brute force","math"],"sample_group":[["3\n1 2 3\n2\n1 2\n2 3","odd\neven"],["4\n1 2 4 3\n4\n1 1\n1 4\n1 4\n2 3","odd\nodd\nodd\neven"]],"created_at":"2026-03-03 11:00:39"}}