Description

Dolphin King is a great man. He can make dolphins do every thing in his control.
One day, he has a whole new idea.
We know each dolphin has different height(when they stand).
He wants to let n dolphins stand in a line and the audience will ask a dolphin a simple question:
How many dolphins shorter than you at the left of you?
But the dolphin thinks too slow. So Dolphin King hopes you can help the poor dolphins to answer the questions.
You are a good guy, please help them.

Input

There are many test cases.
The first line contains a number n(1 <= n <= 50000), which indicates there how many dolphins in this case.
The next line gives you n integers which means the height of each dolphin (numbered from 0 to n-1).

The height of each dolphin is unique.(That is, if a dolphin's height is 5, the others heights will not appear 5.)
The third line contains a number Q(1<=Q<=50000), which means how many people ask problems.
Next Q lines is the question of audience.
Each question has a integer xi that the audience ask.

Output

For each case, output a line with the case number.
Next Q lines each line output the answer of the query.
Output a blank line in the end of each case.

Please refer to the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given several segments of line (int the X axis) with coordinates [L_i,R_i]. You are to choose the minimal amount of them, such they would completely cover the segment [0,M].

Input

The first line is the number of test cases, followed by a blank line.

Each test case in the input should contains an integer M(1<=M<=5000), followed by pairs "L_i R_i"(|L_i|, |R_i|<=50000, i<=100000), each on a separate line. Each test case of input is terminated by pair "0 0".

Each test case will be separated by a single line.

Output

For each test case, in the first line of output your programm should print the minimal number of line segments which can cover segment [0,M]. In the following lines, the coordinates of segments, sorted by their left end (L_i), should be printed in the same format as in the input. Pair "0 0" should not be printed. If [0,M] can not be covered by given line segments, your programm should print "0"(without quotes).

Please print one segment in one single line.

If there are multiple answers using same segments, please print the one with the segment with the most right cooridinate. When there are multiple answer with the same right cooridinate please find the one with the most left coorinate.

Print a blank line between the outputs for two consecutive test cases.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Erin is an engineer. She drives trains. She also arranges the cars within each train. She prefers to put the cars in decreasing order of weight, with the heaviest car at the front of the train.

Unfortunately, sorting train cars is not easy. One cannot simply pick up a car and place it somewhere else. It is impractical to insert a car within an existing train. A car may only be added to the beginning and end of the train.

Cars arrive at the train station in a predetermined order. When each car arrives, Erin can add it to the beginning or end of her train, or refuse to add it at all. The resulting train should be as long as possible, but the cars within it must be ordered by weight.

Given the weights of the cars in the order in which they arrive, what is the longest train that Erin can make?

Input

The first line is the number of test cases to follow. The test cases follow, one after another; the format of each test case is the following:

The first line contains an integer 0 <= n <= 2000, the number of cars. Each of the following n lines contains a non-negative integer giving the weight of a car. No two cars have the same weight.

Output

Output a single integer giving the number of cars in the longest train that can be made with the given restrictions.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called "neighbours." A wall with a window separates adjacent cells, and neighbours can communicate through that window.

All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbours find out, and each communicates this to his other neighbour. That prisoner passes it on to his other neighbour, and so on until they reach a prisoner with no other neighbour (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.

Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.

Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.

Input

The first line of input gives the number of cases, N. N test cases follow. Each case consists of 2 lines. The first line is formatted as
P Q
where P is the number of prison cells and Q is the number of prisoners to be released.
This will be followed by a line with Q distinct cell numbers (of the prisoners to be released), space separated, sorted in ascending order.

1 ≤ N ≤ 100
Q ≤ P
Each cell number is between 1 and P, inclusive.

1 ≤ P ≤ 10000

1 ≤ Q ≤ 100

Output

For each test case, output one line in the format

Case #X: C
where X is the case number, starting from 1, and C is the minimum number of gold coins needed as bribes.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A conveyor belt has a number of vessels of different capacities each filled to brim with milk. The milk from conveyor belt is to be filled into 'm' containers. The constraints are:

 1. Whenever milk from a vessel is poured into a container, the milk in the vessel must be completely poured into that container only. That is          milk from same vessel can not be poured into different containers.
  2.The milk from the vessel must be poured into the container in order which they appear in the conveyor belt. That is, you cannot randomly          pick up a vessel from the conveyor belt and fill the container.
  3. The i-th container must be filled with milk only from those vessels that appear earlier to those that fill jth container, for all i < j

Given the number of containers 'm', you have to fill the containers with milk from all the vessels, without leaving any milk in the vessel. The containers need not necessarily have same capacity. You are given the liberty to assign any possible capacities to them. Your job is to find out the minimal possible capacity of the container which has maximal capacity. (If this sounds confusing, read down for more explanations.)

Input

A single test case consist of 2 lines. The first line specifies 1<=n<=1000 the number of vessels in the conveyor belt and then 'm' which specifies the number of containers to which, you have to transfer the milk. (1 <= m <= 1000000) .The next line contains, the capacity 1<=c<=1000000 of each vessel in order which they appear in the conveyor belt. Note that, milk is filled to the brim of any vessel. So the capacity of the vessel is equal to the amount of milk in it. There are several test cases terminated by EOF.

Output

For each test case, print the minimal possible capacity of the container with maximal capacity. That is there exists a maximal capacity of the containers, below which you can not fill the containers without increasing the number of containers. You have to find such capacity and print it on a single line.

Explanation of the output:
Here you are given 3 vessels at your disposal, for which you are free to assign the capacity. You can transfer, {1 2 3} to the first container, {4} to the second, {5} to third. Here the maximal capacity of the container is the first one which has a capacity of 6. Note that this is optimal too. That is, you can not have the maximal container, have a capacity, less than 6 and still use 3 containers only and fill the containers with all milk.

For the second one, the optimal way is, {4 78} into the first container, and {9} to the second container. So the minimal value of the maximal capacity is 82. Note that {4} to first container and {78 9} to the second is not optimal as, there exists a way to have an assignement of maximal capacity to 82, as opposed to 87 in this case.

Sample Input  Download

Sample Output  Download

Tags

Discuss