C Programming Language

Problem Title: Free Holiday Trip Lottery

SOLVE IN LESS THAN O(n^2) TIME

Lili suddenly found a strange paper inside her wallet. She never saw the paper before. As she curious with that paper, she finally open that paper.

The paper contains the following text. Congratulations, you get a lucky lottery to win a trip to any place you want. You are so lucky because this prize is eligible for two person. You can get the lucky lottery easily. There is a mathematical contest on 1st of February 2020. The question will be explained later by email. Please register your email by sending a text message to the phone number behind this paper. Without further ado, she gives her email address.

After a while, Lili gets the question. She will be given N integers followed by Q num- ber of queries. For each query, it contains an integer M as a certain limitation. For

any value of M, you must find out how many unique pairs which if we add that pair elements, the result is not less than M. Those pair should have the same parity. The same parity happen when the elements of the pair is all odd numbers or all even numbers. Lili wants to design a program that can find the answer of the challenge efficiently as the contest is about how quick you answer the question correctly. She wants to win the prize because she likes to get a holiday prize. Help her to fullfill her dream.

Format Input

Input consists of one integer N, number of Ai in the list. The next line contains N integers Ai. On the next line, given integers Q, number of query given. The next Q lines

contains an integer M - the limitation as described above.

Format Output

Output should be expressed in format Case #X: Y1 Y2 - X is the number of test case, and followed by Y1 and Y2 - number of odd parity pairs and number of even parity pairs, respectively.

Constraints

1 N 10000 1 Q 100 1 M 1000000000 1 Ai 1000000000

SOLVE IN LESS THAN O(n^2) TIME

Sample Input & Output (standard input & output)

5

5 4 3 2 1

3

7

Case #1: 1 0

6

Case #2: 2 1

5

Case #3: 2 1

PLEASE SOLVE IN LESS THAN O(n^2) TIME