Yash Goes to Bank
All submissions for this problem are available.Mr. Srinivasan Pillai - CEO of National Bank of India (NBI) comes up with a plan to provide a free international trip to some of its customers that have done the highest number of financial transactions annually. The bank has $400$ unique lottery tickets, each with a unique ticket Id. NBI is a very famous bank in India and has a large number of customers engaged with it. At the beginning of each year, bank randomly associates the account number of each Indian customer with a lottery ticket. At the end of the year, the bank chooses $N$ customers (i.e. account numbers) for deciding lucky winners. Let array $A$ of size $N$ represent these account numbers. To decide lucky winners, Mr. Pillai takes the help of his Manager - Mr. Rathan Vyas. Mr. Vyas needs to compute a number $L$, which in turn is used by the Bank to declare lucky winners using some unknown secret strategy. In order to calculate $L$, first Mr. Vyas replaces the account numbers in the array $A$ with the corresponding ticket Id’s associated with each account. Let the new array be named as $B$. Then, Mr. Pillai chooses $2$ numbers: $l$ and $r$ (such that $l < r$). Furthermore, Mr. Vyas considers the sorted array $S$ of all the elements in the index range $[l , r]$ of the array $B$, $l$ and $r$ inclusive. Finally, he computes $L$ by adding all the ticket Id’s at odd indices of $S$ and subtracting all the ticket Id’s at even indices from it. Your task is to help Mr. Vyas in generating $L$. ###Constraints: - $1 \leq N \leq10000$ - $1 \leq B[i] \leq 1000000000$ - $1 \leq q \leq 100000$ The array $B$ contains no more than $400$ distinct integers. ###Input: - The $1$$st$ line of input contains a single number $N$. - The $2$$nd$ line of input contains $N$ space separated integers representing the array $B$. - The third line contains an integer $q$ representing number of queries to be performed on $B$. - Next $q$ lines contain two space-separated integers $l$ and $r$. ###Output: The output contains $q$ lines. Each line consisting of a single integer $L$ corresponding to each query. ###Sample Input 4 2 1 3 4 2 1 2 2 2 ###Sample Output -1 1 ###Explanation - $1$$st$ query has indices $l=1$ and $r=2$. So, consider $[2 1]$ part of $B$ in range $[1,2]$. $S$ will be $[1 2].$ Now, $L$ = +1 -2 => $L$ = -1. - $2$$nd$ query has $l$=2 and $r$=2. So, $$ is part of $B$ to be considered in range $[2, 2]$. $S$ will be $.$ Now, $L$= +1 => $L$ = +1.
|Time Limit:||2.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions