VOI (Vietnam National Olympiad in Informatics) 2016 has just ended a few hours ago. You are given 6 problems (3 each day) to solve in the time of 180 minutes per day. As a contestant, I must say for such a small window of time I just couldn't do them all. Anyways here are the (of course, shortened version of) statements of the problems.

The problems have a total score of 40, which divides to 6 / 7 / 7 per day.

### Day 1

#### Problem 1 (6 pts)

You are given a sequence of numbers *A*[1..*n*] (1 ≤ *A*_{i} ≤ 10^{9}). You have to erase the least amount of numbers in the sequence such that for every *i* < *j* in the new sequence the following condition holds: .

50% of the tests have *n* ≤ 20. The remaining have *n* ≤ 2000.

#### Problem 2 (7 pts)

There is a road which has a length of *L*. You have a truck with the fuel tank capacity of *K*, and start off with *Q* litres of fuel at one side (point 0) which you will have to deliver to the other side (point L) of the road. Your truck consumes 1 litre of fuel per unit of length it travels. In order to help you, starting from point 0 there is a fuel tank with unlimited capacity every *D* units of length (so there are tanks on point *D*, 2*D*, ... and they are empty at start). You are allowed to transfer the fuel in and out of any tank. Maximize the amount of fuel you can deliver to point *L*.

Given *L*, *K*, *Q*, *D*, calculate the maximum amount of fuel you can deliver to point *L*.

Constraints: 1 ≤ *L*, *K*, *D* ≤ 10^{9}, 1 ≤ *Q* ≤ 10^{12}. On the first 50% of the tests .

#### Problem 3 (7 pts)

You are given an undirected connected graph *G*(*V*, *E*) of *n* vertices and *m* edges (with no self edges and multi-edges) and the following algorithm to construct *K*:

First, initialize

*K*[1..*n*] as an array of empty vectors of integers. Let*K*[1] = {0}.Let

*f*[1..*n*] be an array of booleans, all being false at start. Let*Q*be a set of indices*i*such that*f*[*i*] =*false*and |*K*[*i*]| > 0While |

*Q*| > 0:- Let
*u*be the smallest number in*Q*. Set*f*[*u*] =*true*

- For each edge (
*u*,*v*) in*G*such that*f*[*v*] =*false*we append*u*into back of*K*[*v*].

- Let

Please renumber all the vertices in the graph so that for the resulting array *K* of the algorithm the following condition holds: For every *u* < *v* we have *K*[*u*] ≤ *K*[*v*] alphabetically.

Constraints: 40% of the tests have *n* ≤ 10. 80% of the tests have *n* ≤ 10^{3}, *m* ≤ 10^{4}. All tests have *n* ≤ 2 × 10^{4}, *m* ≤ 10^{6}.

### Day 2

#### Problem 1 (6 pts)

You are given a grid of *n* × *m* cells, each containing a zero or one. Find the diamond-shaped area (which has to be fully inside the grid) containing the most ones such that no two one cells inside the area share the same edge.

A diamond-shaped area with center (*x*_{0}, *y*_{0}) and radius *r* is a set of cells (*x*, *y*) which satisfies |*x* - *x*_{0}| + |*y* - *y*0| ≤ *r*.

Constraints: 40% of the tests have *n* ≤ 100. 80% of the tests have *n* ≤ 500. All tests have *n* ≤ 1000.

#### Problem 2 (7 pts)

You are given a set of *n* operations containing at most 4 numbers within [0..10^{6}] and operators `+`

, `-`

, `*`

. You have add brackets to some of the equations such that each of them has an unique value.

Constraints: 50% of the tests have *n* ≤ 20 and operations having at most 3 numbers. All tests have *n* ≤ 2000.

#### Problem 3 (7 pts)

You are given *n* trees (real world trees) with the *i*-th tree having height *h*_{i} and stands at position *i* and you have to fall down all of them. Falling the tree *i* to the left causes all trees *j* with *i* - *h*_{i} < *j* < *i* to fall to the left, and falling tree *i* to the right causes all trees *j* with *i* < *j* < *i* + *h*_{i} to fall to the right (and they to make chains like dominoes). Find a way of cutting the trees such that the number of trees manually fell at minimized.

All trees have height not exceeding 4 × 10^{6}

Constraints: 40% of the tests have *n* ≤ 10^{4}, 80% of the tests have *n* ≤ 10^{5}, all tests have *n* ≤ 4 × 10^{6}