You are given $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. Find the maximum value of $$$max(a_l, a_{l + 1}, \ldots, a_r) \cdot min(a_l, a_{l + 1}, \ldots, a_r)$$$ over all pairs $$$(l, r)$$$ of integers for which $$$1 \le l \lt r \le n$$$.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$).
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.
For each test case, print a single integer — the maximum possible value of the product from the statement.
4 3 2 4 3 4 3 2 3 1 2 69 69 6 719313 273225 402638 473783 804745 323328
12 6 4761 381274500335
Let $$$f(l, r) = max(a_l, a_{l + 1}, \ldots, a_r) \cdot min(a_l, a_{l + 1}, \ldots, a_r)$$$.
In the first test case,
- $$$f(1, 2) = max(a_1, a_2) \cdot min(a_1, a_2) = max(2, 4) \cdot min(2, 4) = 4 \cdot 2 = 8$$$.
- $$$f(1, 3) = max(a_1, a_2, a_3) \cdot min(a_1, a_2, a_3) = max(2, 4, 3) \cdot min(2, 4, 3) = 4 \cdot 2 = 8$$$.
- $$$f(2, 3) = max(a_2, a_3) \cdot min(a_2, a_3) = max(4, 3) \cdot min(4, 3) = 4 \cdot 3 = 12$$$.
So the maximum is $$$f(2, 3) = 12$$$.
In the second test case, the maximum is $$$f(1, 2) = f(1, 3) = f(2, 3) = 6$$$.
You are given an array $$$a$$$ consisting of $$$n$$$ integers.
Let's call a pair of indices $$$i$$$, $$$j$$$ good if $$$1 \le i \lt j \le n$$$ and $$$\gcd(a_i, 2a_j) \gt 1$$$ (where $$$\gcd(x, y)$$$ is the greatest common divisor of $$$x$$$ and $$$y$$$).
Find the maximum number of good index pairs if you can reorder the array $$$a$$$ in an arbitrary way.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.
The first line of the test case contains a single integer $$$n$$$ ($$$2 \le n \le 2000$$$) — the number of elements in the array.
The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.
For each test case, output a single integer — the maximum number of good index pairs if you can reorder the array $$$a$$$ in an arbitrary way.
3 4 3 6 5 3 2 1 7 5 1 4 2 4 1
4 0 9
In the first example, the array elements can be rearranged as follows: $$$[6, 3, 5, 3]$$$.
In the third example, the array elements can be rearranged as follows: $$$[4, 4, 2, 1, 1]$$$.
We will consider the numbers $$$a$$$ and $$$b$$$ as adjacent if they differ by exactly one, that is, $$$|a-b|=1$$$.
We will consider cells of a square matrix $$$n \times n$$$ as adjacent if they have a common side, that is, for cell $$$(r, c)$$$ cells $$$(r, c-1)$$$, $$$(r, c+1)$$$, $$$(r-1, c)$$$ and $$$(r+1, c)$$$ are adjacent to it.
For a given number $$$n$$$, construct a square matrix $$$n \times n$$$ such that:
- Each integer from $$$1$$$ to $$$n^2$$$ occurs in this matrix exactly once;
- If $$$(r_1, c_1)$$$ and $$$(r_2, c_2)$$$ are adjacent cells, then the numbers written in them must not be adjacent.
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$). Then $$$t$$$ test cases follow.
Each test case is characterized by one integer $$$n$$$ ($$$1 \le n \le 100$$$).
For each test case, output:
- -1, if the required matrix does not exist;
- the required matrix, otherwise (any such matrix if many of them exist).
The matrix should be outputted as $$$n$$$ lines, where each line contains $$$n$$$ integers.
3 1 2 3
1 -1 2 9 7 4 6 3 1 8 5
You have $$$n$$$ students under your control and you have to compose exactly two teams consisting of some subset of your students. Each student had his own skill, the $$$i$$$-th student skill is denoted by an integer $$$a_i$$$ (different students can have the same skills).
So, about the teams. Firstly, these two teams should have the same size. Two more constraints:
- The first team should consist of students with distinct skills (i.e. all skills in the first team are unique).
- The second team should consist of students with the same skills (i.e. all skills in the second team are equal).
Note that it is permissible that some student of the first team has the same skill as a student of the second team.
Consider some examples (skills are given):
- $$$[1, 2, 3]$$$, $$$[4, 4]$$$ is not a good pair of teams because sizes should be the same;
- $$$[1, 1, 2]$$$, $$$[3, 3, 3]$$$ is not a good pair of teams because the first team should not contain students with the same skills;
- $$$[1, 2, 3]$$$, $$$[3, 4, 4]$$$ is not a good pair of teams because the second team should contain students with the same skills;
- $$$[1, 2, 3]$$$, $$$[3, 3, 3]$$$ is a good pair of teams;
- $$$[5]$$$, $$$[6]$$$ is a good pair of teams.
Your task is to find the maximum possible size $$$x$$$ for which it is possible to compose a valid pair of teams, where each team size is $$$x$$$ (skills in the first team needed to be unique, skills in the second team should be the same between them). A student cannot be part of more than one team.
You have to answer $$$t$$$ independent test cases.
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.
The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of students. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ is the skill of the $$$i$$$-th student. Different students can have the same skills.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).
For each test case, print the answer — the maximum possible size $$$x$$$ for which it is possible to compose a valid pair of teams, where each team size is $$$x$$$.
4 7 4 2 4 1 4 3 4 5 2 1 5 4 3 1 1 4 1 1 1 3
3 1 0 2
In the first test case of the example, it is possible to construct two teams of size $$$3$$$: the first team is $$$[1, 2, 4]$$$ and the second team is $$$[4, 4, 4]$$$. Note, that there are some other ways to construct two valid teams of size $$$3$$$.
You are a game designer and want to make an obstacle course. The player will walk from left to right. You have $$$n$$$ heights of mountains already selected and want to arrange them so that the absolute difference of the heights of the first and last mountains is as small as possible.
In addition, you want to make the game difficult, and since walking uphill or flat is harder than walking downhill, the difficulty of the level will be the number of mountains $$$i$$$ ($$$1 \leq i \lt n$$$) such that $$$h_i \leq h_{i+1}$$$ where $$$h_i$$$ is the height of the $$$i$$$-th mountain. You don't want to waste any of the mountains you modelled, so you have to use all of them.
From all the arrangements that minimize $$$|h_1-h_n|$$$, find one that is the most difficult. If there are multiple orders that satisfy these requirements, you may find any.
The first line will contain a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. Then $$$t$$$ test cases follow.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of mountains.
The second line of each test case contains $$$n$$$ integers $$$h_1,\ldots,h_n$$$ ($$$1 \leq h_i \leq 10^9$$$), where $$$h_i$$$ is the height of the $$$i$$$-th mountain.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output $$$n$$$ integers — the given heights in an order that maximizes the difficulty score among all orders that minimize $$$|h_1-h_n|$$$.
If there are multiple orders that satisfy these requirements, you may output any.
2 4 4 2 1 2 2 3 1
2 4 1 2 1 3
In the first test case:
The player begins at height $$$2$$$, next going up to height $$$4$$$ increasing the difficulty by $$$1$$$. After that he will go down to height $$$1$$$ and the difficulty doesn't change because he is going downhill. Finally the player will go up to height $$$2$$$ and the difficulty will increase by $$$1$$$. The absolute difference between the starting height and the end height is equal to $$$0$$$ and it's minimal. The difficulty is maximal.
In the second test case:
The player begins at height $$$1$$$, next going up to height $$$3$$$ increasing the difficulty by $$$1$$$. The absolute difference between the starting height and the end height is equal to $$$2$$$ and it's minimal as they are the only heights. The difficulty is maximal.
Alice and Bob are playing a game on a matrix, consisting of $$$2$$$ rows and $$$m$$$ columns. The cell in the $$$i$$$-th row in the $$$j$$$-th column contains $$$a_{i, j}$$$ coins in it.
Initially, both Alice and Bob are standing in a cell $$$(1, 1)$$$. They are going to perform a sequence of moves to reach a cell $$$(2, m)$$$.
The possible moves are:
- Move right — from some cell $$$(x, y)$$$ to $$$(x, y + 1)$$$;
- Move down — from some cell $$$(x, y)$$$ to $$$(x + 1, y)$$$.
First, Alice makes all her moves until she reaches $$$(2, m)$$$. She collects the coins in all cells she visit (including the starting cell).
When Alice finishes, Bob starts his journey. He also performs the moves to reach $$$(2, m)$$$ and collects the coins in all cells that he visited, but Alice didn't.
The score of the game is the total number of coins Bob collects.
Alice wants to minimize the score. Bob wants to maximize the score. What will the score of the game be if both players play optimally?
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.
Then the descriptions of $$$t$$$ testcases follow.
The first line of the testcase contains a single integer $$$m$$$ ($$$1 \le m \le 10^5$$$) — the number of columns of the matrix.
The $$$i$$$-th of the next $$$2$$$ lines contain $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$1 \le a_{i,j} \le 10^4$$$) — the number of coins in the cell in the $$$i$$$-th row in the $$$j$$$-th column of the matrix.
The sum of $$$m$$$ over all testcases doesn't exceed $$$10^5$$$.
For each testcase print a single integer — the score of the game if both players play optimally.
3 3 1 3 7 3 5 1 3 1 3 9 3 5 1 1 4 7
7 8 0
The paths for the testcases are shown on the following pictures. Alice's path is depicted in red and Bob's path is depicted in blue.
You have an array $$$a$$$ of length $$$n$$$. For every positive integer $$$x$$$ you are going to perform the following operation during the $$$x$$$-th second:
- Select some distinct indices $$$i_{1}, i_{2}, \ldots, i_{k}$$$ which are between $$$1$$$ and $$$n$$$ inclusive, and add $$$2^{x-1}$$$ to each corresponding position of $$$a$$$. Formally, $$$a_{i_{j}} := a_{i_{j}} + 2^{x-1}$$$ for $$$j = 1, 2, \ldots, k$$$. Note that you are allowed to not select any indices at all.
You have to make $$$a$$$ nondecreasing as fast as possible. Find the smallest number $$$T$$$ such that you can make the array nondecreasing after at most $$$T$$$ seconds.
Array $$$a$$$ is nondecreasing if and only if $$$a_{1} \le a_{2} \le \ldots \le a_{n}$$$.
You have to answer $$$t$$$ independent test cases.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases.
The first line of each test case contains single integer $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — the length of array $$$a$$$. It is guaranteed that the sum of values of $$$n$$$ over all test cases in the input does not exceed $$$10^{5}$$$.
The second line of each test case contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$-10^{9} \le a_{i} \le 10^{9}$$$).
For each test case, print the minimum number of seconds in which you can make $$$a$$$ nondecreasing.
341 7 6 551 2 3 4 520 -4
2 0 3
In the first test case, if you select indices $$$3, 4$$$ at the $$$1$$$-st second and $$$4$$$ at the $$$2$$$-nd second, then $$$a$$$ will become $$$[1, 7, 7, 8]$$$. There are some other possible ways to make $$$a$$$ nondecreasing in $$$2$$$ seconds, but you can't do it faster.
In the second test case, $$$a$$$ is already nondecreasing, so answer is $$$0$$$.
In the third test case, if you do nothing at first $$$2$$$ seconds and select index $$$2$$$ at the $$$3$$$-rd second, $$$a$$$ will become $$$[0, 0]$$$.
Quite recently a creative student Lesha had a lecture on trees. After the lecture Lesha was inspired and came up with the tree of his own which he called a k-tree.
A k-tree is an infinite rooted tree where:
- each vertex has exactly k children;
- each edge has some weight;
- if we look at the edges that goes from some vertex to its children (exactly k edges), then their weights will equal 1, 2, 3, ..., k.
The picture below shows a part of a 3-tree.
Help Dima find an answer to his question. As the number of ways can be rather large, print it modulo 1000000007 (109 + 7).
A single line contains three space-separated integers: n, k and d (1 ≤ n, k ≤ 100; 1 ≤ d ≤ k).
Print a single integer — the answer to the problem modulo 1000000007 (109 + 7).
3 3 2
3
3 3 3
1
4 3 2
6
4 5 2
7
You've got array a[1], a[2], ..., a[n], consisting of n integers. Count the number of ways to split all the elements of the array into three contiguous parts so that the sum of elements in each part is the same.
More formally, you need to find the number of such pairs of indices i, j (2 ≤ i ≤ j ≤ n - 1), that 
.
The first line contains integer n (1 ≤ n ≤ 5·105), showing how many numbers are in the array. The second line contains n integers a[1], a[2], ..., a[n] (|a[i]| ≤ 109) — the elements of array a.
Print a single integer — the number of ways to split the array into three parts with the same sum.
5
1 2 3 0 3
2
4
0 1 -1 0
1
2
4 1
0
You have r red, g green and b blue balloons. To decorate a single table for the banquet you need exactly three balloons. Three balloons attached to some table shouldn't have the same color. What maximum number t of tables can be decorated if we know number of balloons of each color?
Your task is to write a program that for given values r, g and b will find the maximum number t of tables, that can be decorated in the required manner.
The single line contains three integers r, g and b (0 ≤ r, g, b ≤ 2·109) — the number of red, green and blue baloons respectively. The numbers are separated by exactly one space.
Print a single integer t — the maximum number of tables that can be decorated in the required manner.
5 4 3
4
1 1 1
1
2 3 3
2
In the first sample you can decorate the tables with the following balloon sets: "rgg", "gbb", "brr", "rrg", where "r", "g" and "b" represent the red, green and blue balls, respectively.
This is yet another problem dealing with regular bracket sequences.
We should remind you that a bracket sequence is called regular, if by inserting «+» and «1» into it we can get a correct mathematical expression. For example, sequences «(())()», «()» and «(()(()))» are regular, while «)(», «(()» and «(()))(» are not.
You are given a string of «(» and «)» characters. You are to find its longest substring that is a regular bracket sequence. You are to find the number of such substrings as well.
The first line of the input file contains a non-empty string, consisting of «(» and «)» characters. Its length does not exceed 106.
Print the length of the longest substring that is a regular bracket sequence, and the number of such substrings. If there are no such substrings, write the only line containing "0 1".
)((())))(()())
6 2
))(
0 1
The only difference between the two versions is that in this version $$$n \leq 1000$$$ and the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.
A terminal is a row of $$$n$$$ equal segments numbered $$$1$$$ to $$$n$$$ in order. There are two terminals, one above the other.
You are given an array $$$a$$$ of length $$$n$$$. For all $$$i = 1, 2, \dots, n$$$, there should be a straight wire from some point on segment $$$i$$$ of the top terminal to some point on segment $$$a_i$$$ of the bottom terminal. You can't select the endpoints of a segment. For example, the following pictures show two possible wirings if $$$n=7$$$ and $$$a=[4,1,4,6,7,7,5]$$$.
A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red.
What is the maximum number of crossings there can be if you place the wires optimally?
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.
The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the length of the array.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array.
The sum of $$$n$$$ across all test cases does not exceed $$$1000$$$.
For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.
474 1 4 6 7 7 522 11132 2 2
6 1 0 3
The first test case is shown in the second picture in the statement.
In the second test case, the only wiring possible has the two wires cross, so the answer is $$$1$$$.
In the third test case, the only wiring possible has one wire, so the answer is $$$0$$$.
The only difference between the two versions is that in this version $$$n \leq 2 \cdot 10^5$$$ and the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
A terminal is a row of $$$n$$$ equal segments numbered $$$1$$$ to $$$n$$$ in order. There are two terminals, one above the other.
You are given an array $$$a$$$ of length $$$n$$$. For all $$$i = 1, 2, \dots, n$$$, there should be a straight wire from some point on segment $$$i$$$ of the top terminal to some point on segment $$$a_i$$$ of the bottom terminal. You can't select the endpoints of a segment. For example, the following pictures show two possible wirings if $$$n=7$$$ and $$$a=[4,1,4,6,7,7,5]$$$.
A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red.
What is the maximum number of crossings there can be if you place the wires optimally?
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.
The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array.
The sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.
474 1 4 6 7 7 522 11132 2 2
6 1 0 3
The first test case is shown in the second picture in the statement.
In the second test case, the only wiring possible has the two wires cross, so the answer is $$$1$$$.
In the third test case, the only wiring possible has one wire, so the answer is $$$0$$$.