An online grocery store introduces a new product: you can buy a box of seven bananas of different ripeness, such that the first banana becomes ripe on some day, the second one — on the following day, the third — on the following day after the second one, and so on. Formally speaking, the box contains exactly seven bananas, the first one of which becomes ripe on day $$$d$$$, the second one — on day $$$d + 1$$$, the third — on day $$$d + 2$$$, the fourth — on day $$$d + 3$$$, the fifth — on day $$$d + 4$$$, the sixth — on day $$$d + 5$$$, and the seventh — on day $$$d + 6$$$.
A set of bananas was delivered to the storehouse. According to the delivery note, you know that each banana is going to become ripe on one of the following $$$n$$$ days, and for each day $$$i$$$ from 1 to $$$n$$$, you are given that $$$a_i$$$ of delivered bananas are going to become ripe on day $$$i$$$.
You task is to make the maximum number of boxes of bananas. Calculate the maximum number of boxes you are able to make, as well as the number of bananas that will remain out of the boxes.
The first line contains an integer $$$n$$$ — the number of days in the delivery note ($$$7 \le n \le 100$$$).
The second line contains $$$n$$$ integers $$$a_i$$$ — the number of bananas that become ripe on day $$$i$$$ ($$$0 \le a_i \le 10^9$$$).
Print two integers: the maximum number of boxes of bananas, and the number of bananas left.
| Subtask | Score | Constraints |
| 1 | 30 | $$$n = 7$$$; $$$a_i \le 100$$$ |
| 2 | 45 | $$$n \le 100$$$; $$$a_i \le 1000$$$ |
| 3 | 25 | $$$n \le 100$$$; $$$a_i \le 10^9$$$ |
9 4 3 5 4 5 4 4 5 2
4 8
7 2 3 3 3 2 2 3
2 4
In the first example, one of the ways is to make two boxes with $$$d = 1$$$, one box with $$$d = 2$$$, and one box with $$$d = 3$$$. Note that there are other ways to make 4 boxes.
In the second example, it's possible to make two boxes with $$$d = 1$$$.
Recently Manya learned that a permutation is a sequence of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$2,3,1,5,4$$$ is a permutation, but $$$1,2,2$$$ is not a permutation ($$$2$$$ appears twice) and $$$1,3,4$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the sequence).
Manya started to write down random permutations, one under another. She wrote down $$$n-1$$$ permutations and realized that a column in the resulting table of integers can also turn out to be a permutation when Manya writes down the $$$n$$$th permutation. Every column will consist of $$$n$$$ integers from $$$1$$$ to $$$n$$$, however, not every column will be a valid permutation. Then Many decided to add the $$$n$$$th permutation in a way to maximize the number of columns-permutations.
Your task is to find out the maximum number of columns that could be permutations after adding the $$$n$$$th permutation; and how many permutations will result in the highest number of columns-permutations.
The first line contains a single integer $$$n$$$ — the permutation length ($$$2 \le n \le 1000$$$).
Each of the next $$$n-1$$$ lines contains a permutation of length $$$n$$$ — $$$n$$$ integers from $$$1$$$ to $$$n$$$.
Output two integers — the maximum number of column-permutations that can be achieved after adding a permutation; and the number of permutations that can be added to achieve the highest number of columns-permutations modulo $$$10^9 + 7$$$.
| Subtask | Score | Constraints |
| 1 | 20 | $$$n \le 7$$$ |
| 2 | 45 | $$$n \le 300$$$ |
| 3 | 35 | $$$n \le 1000$$$ |
4 1 2 3 4 4 1 2 3 3 2 4 1
2 4
4 1 2 3 4 1 2 4 3 2 1 4 3
0 24
In the first example, the first column needs $$$2$$$ to be a permutation as well as the fourth column, the third column needs $$$1$$$. Manya can add permutations:
$$$2,3,1,4$$$;
$$$2,4,1,3$$$;
$$$3,4,1,2$$$;
$$$4,3,1,2$$$;
to get two columns-permutations. It is not possible to get a result with three columns-permutations as the $$$n$$$th permutation can not contain two $$$2$$$.
In the second example, none of the columns will be a valid permutation, no matter what permutation Manya adds. That means that the maximum number of columns-permutations is $$$0$$$ and can be achieved by adding any of the $$$24$$$ permutations.
Azat wondered how many pairs of integer roots $$$(x_1, x_2)$$$ of the quadratic equation $$$x^2 + bx + c = 0$$$ exist, when the sum of coefficients $$$b$$$ and $$$c$$$ is between $$$l$$$ and $$$r$$$, that is, $$$l \le b + c \le r$$$ ($$$b$$$, $$$c$$$, $$$l$$$, $$$r$$$ are all integers). Pairs of roots $$$(x_1, x_2)$$$ and $$$(x_2, x_1)$$$ are considered the same.
Help Azat find out the answer to his problem.
The first line contains two integers $$$l$$$ and $$$r$$$ ($$$-10^{12} \le l \le r \le 10^{12}$$$; $$$r - l \le 10^6$$$).
Print a single number — the number of pairs of integer roots, if there are an infinite number of pairs of integer roots, print -1.
| Subtask | Score | Constraints |
| $$$1$$$ | $$$8$$$ | $$$l = r$$$ and $$$|l| \le 10^3$$$ |
| $$$2$$$ | $$$9$$$ | $$$r - l \le 2 \cdot 10^3$$$ and $$$|l|, |r| \le 10^3$$$ |
| $$$3$$$ | $$$13$$$ | $$$l = r$$$ and $$$|l| \le 10^6$$$ |
| $$$4$$$ | $$$20$$$ | $$$r - l \le 2 \cdot 10^2$$$ and $$$|l|, |r| \le 10^{8}$$$ |
| $$$5$$$ | $$$16$$$ | $$$l = r$$$ and $$$|l| \le 10^{12}$$$ |
| $$$6$$$ | $$$34$$$ | $$$r - l \le 10^6$$$ and $$$|l|, |r| \le 10^{12}$$$ |
7 7
4
-2 -2
1
-7 -3
13
For $$$l = r = 7$$$, there are four pairs of roots: $$$(2, 9), (0, -7), (3, 5), (-1, -3)$$$.
For the 2 and 9 pair, the equation is $$$x^2 - 11 \cdot x + 18 = 0$$$.
For the 0 and -7 pair, the equation is $$$x^2 + 7 \cdot x + 0 = 0$$$.
For the 3 and 5 pair, the equation is $$$x^2 - 8 \cdot x + 15 = 0$$$.
For the $$$-1$$$ and $$$-3$$$ pair, the equation is $$$x^2 + 4 \cdot x + 3 = 0$$$.
In all four cases, the sum of $$$b$$$ and $$$c$$$ is equal to $$$7$$$.
You are given an array of non-negative integers $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$. Count number of triplets $$$1 \le i \lt j \lt k \le n$$$, such that $$$(a_i \oplus a_j) \lt (a_j \oplus a_k)$$$, where $$$\oplus$$$ is an exclusive OR (XOR) operation.
The first line contains a single integer $$$n$$$ — the number of elements in the array ($$$3 \le n \le 200\,000$$$).
The second line contains $$$n$$$ integer numbers $$$a_i$$$ — elements of the array ($$$0 \le a_i \le 10^{18}$$$).
Output single integer — the number of triplets.
| Subtask | Score | Constraints |
| $$$1$$$ | $$$17$$$ | $$$n \le 100$$$ |
| $$$2$$$ | $$$19$$$ | $$$n \le 3\,000$$$ |
| $$$3$$$ | $$$18$$$ | $$$n \le 30\,000$$$, $$$a_i \le 50$$$ |
| $$$4$$$ | $$$22$$$ | $$$n \le 30\,000$$$ |
| $$$5$$$ | $$$24$$$ | No additional constraints |
3 0 1 2
1
4 0 1 2 3
2
5 6 1 17 3 11
7
10 0 1 2 3 4 5 6 7 8 9
84