This is the easy version of this problem. In this version, we do not have queries. Note that we have multiple test cases in this version. You can make hacks only if both versions of the problem are solved.
An array $$$b$$$ of length $$$m$$$ is good if for all $$$i$$$ the $$$i$$$-th element is greater than or equal to $$$i$$$. In other words, $$$b$$$ is good if and only if $$$b_i \geq i$$$ for all $$$i$$$ ($$$1 \leq i \leq m$$$).
You are given an array $$$a$$$ consisting of $$$n$$$ positive integers. Find the number of pairs of indices $$$(l, r)$$$, where $$$1 \le l \le r \le n$$$, such that the array $$$[a_l, a_{l+1}, \ldots, a_r]$$$ is good.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$). Description of the test cases follows.
The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the length of the array $$$a$$$.
The second line of each test case contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$), representing the array $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print the number of suitable pairs of indices.
331 2 331 1 142 1 4 3
6 3 7
In the first test case, all subarrays of $$$a$$$ are good, so all pairs are suitable.
In the second test case, the pairs $$$(1, 1)$$$, $$$(2, 2)$$$, and $$$(3, 3)$$$ are suitable. For example, when $$$(l, r) = (1, 2)$$$, the array $$$b=[1,1]$$$ is not good because $$$b_2 \lt 2$$$.
The legendary Farmer John is throwing a huge party, and animals from all over the world are hanging out at his house. His guests are hungry, so he instructs his cow Bessie to bring out the snacks! Moo!
There are $$$n$$$ snacks flavors, numbered with integers $$$1, 2, \ldots, n$$$. Bessie has $$$n$$$ snacks, one snack of each flavor. Every guest has exactly two favorite flavors. The procedure for eating snacks will go as follows:
- First, Bessie will line up the guests in some way.
- Then in this order, guests will approach the snacks one by one.
- Each guest in their turn will eat all remaining snacks of their favorite flavor. In case no favorite flavors are present when a guest goes up, they become very sad.
Help Bessie to minimize the number of sad guests by lining the guests in an optimal way.
The first line contains integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le 10^5$$$), the number of snacks and the number of guests.
The $$$i$$$-th of the following $$$k$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$), favorite snack flavors of the $$$i$$$-th guest.
Output one integer, the smallest possible number of sad guests.
5 4 1 2 4 3 1 4 3 4
1
6 5 2 3 2 1 3 4 6 5 4 5
0
In the first example, Bessie can order the guests like this: $$$3, 1, 2, 4$$$. Guest $$$3$$$ goes first and eats snacks $$$1$$$ and $$$4$$$. Then the guest $$$1$$$ goes and eats the snack $$$2$$$ only, because the snack $$$1$$$ has already been eaten. Similarly, the guest $$$2$$$ goes up and eats the snack $$$3$$$ only. All the snacks are gone, so the guest $$$4$$$ will be sad.
In the second example, one optimal ordering is $$$2, 1, 3, 5, 4$$$. All the guests will be satisfied.
Vanya has a graph with $$$n$$$ vertices (numbered from $$$1$$$ to $$$n$$$) and an array $$$a$$$ of $$$n$$$ integers; initially, there are no edges in the graph. Vanya got bored, and to have fun, he decided to perform $$$n - 1$$$ operations.
Operation number $$$x$$$ (operations are numbered in order starting from $$$1$$$) is as follows:
- Choose $$$2$$$ different numbers $$$1 \leq u,v \leq n$$$, such that $$$|a_u - a_v|$$$ is divisible by $$$x$$$.
- Add an undirected edge between vertices $$$u$$$ and $$$v$$$ to the graph.
Help Vanya get a connected$$$^{\text{∗}}$$$ graph using the $$$n - 1$$$ operations, or determine that it is impossible.
$$$^{\text{∗}}$$$A graph is called connected if it is possible to reach any vertex from any other by moving along the edges.
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{3}$$$) — the number of test cases. Then follows the description of the test cases.
The first line of each test case contains the number $$$n$$$ ($$$1 \leq n \leq 2000$$$) — the number of vertices in the graph.
The second line of each test case contains $$$n$$$ numbers $$$a_1, a_2, \cdots a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.
For each test case, if there is no solution, then output "No" (without quotes).
Otherwise, output "Yes" (without quotes), and then output $$$n - 1$$$ lines, where in the $$$i$$$-th line, output the numbers $$$u$$$ and $$$v$$$ that need to be chosen for operation $$$i$$$.
You can output each letter in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).
821 4499 7 1 13510 2 31 44 73587 6 81 44 32562 35 33 79 1656 51 31 69 42552 63 25 21 51233 40 3 11 31 43 37 8 50 5 12 22
YES 2 1 YES 4 1 2 1 3 2 YES 5 1 4 1 3 1 2 1 YES 4 1 3 1 2 1 5 4 YES 3 1 5 1 2 1 4 2 YES 4 1 5 1 2 1 3 2 YES 2 1 5 2 3 1 4 3 YES 9 1 12 9 11 1 10 1 6 1 7 6 2 1 8 2 5 2 3 1 4 1
Let's consider the second test case.
- First operation $$$(x = 1)$$$: we can connect vertices $$$4$$$ and $$$1$$$, since $$$|a_4 - a_1| = |13 - 99| = |-86| = 86$$$, and $$$86$$$ is divisible by $$$1$$$.
- Second operation $$$(x = 2)$$$: we can connect vertices $$$2$$$ and $$$1$$$, since $$$|a_2 - a_1| = |7 - 99| = |-92| = 92$$$, and $$$92$$$ is divisible by $$$2$$$.
- Third operation $$$(x = 3)$$$: we can connect vertices $$$3$$$ and $$$2$$$, since $$$|a_3 - a_2| = |1 - 7| = |-6| = 6$$$, and $$$6$$$ is divisible by $$$3$$$.
From the picture, it can be seen that a connected graph is obtained.
You have obtained the new limited event character Xilonen. You decide to use her in combat.
There are $$$n$$$ enemies in a line. The $$$i$$$'th enemy from the left has health $$$h_i$$$ and is currently at position $$$x_i$$$. Xilonen has an attack damage of $$$m$$$, and you are ready to defeat the enemies with her.
Xilonen has a powerful "ground stomp" attack. Before you perform any attacks, you select an integer $$$p$$$ and position Xilonen there ($$$p$$$ can be any integer position, including a position with an enemy currently). Afterwards, for each attack, she deals $$$m$$$ damage to an enemy at position $$$p$$$ (if there are any), $$$m-1$$$ damage to enemies at positions $$$p-1$$$ and $$$p+1$$$, $$$m-2$$$ damage to enemies at positions $$$p-2$$$ and $$$p+2$$$, and so on. Enemies that are at least a distance of $$$m$$$ away from Xilonen take no damage from attacks.
Formally, if there is an enemy at position $$$x$$$, she will deal $$$\max(0,m - |p - x|)$$$ damage to that enemy each hit. Note that you may not choose a different $$$p$$$ for different attacks.
Over all possible $$$p$$$, output the minimum number of attacks Xilonen must perform to defeat at least $$$k$$$ enemies. If it is impossible to find a $$$p$$$ such that eventually at least $$$k$$$ enemies will be defeated, output $$$-1$$$ instead. Note that an enemy is considered to be defeated if its health reaches $$$0$$$ or below.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) – the number of test cases.
The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq k \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^9$$$).
The following line contains $$$n$$$ integers $$$h_1, h_2, ..., h_n$$$ ($$$1 \leq h_i \leq 10^9$$$).
The last line of each testcase contains $$$n$$$ integers $$$x_1, x_2, ..., x_n$$$ ($$$1\leq x_i \leq 10^9$$$, $$$x_i \lt x_{i+1}$$$ for all $$$1 \leq i \lt n$$$)
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, output an integer on a new line, the minimum number of attacks that must be performed to defeat at least $$$k$$$ enemies. If it is impossible to find a $$$p$$$ such that eventually at least $$$k$$$ enemies will be defeated, output $$$-1$$$ instead.
65 5 37 7 7 7 71 2 3 4 59 5 92 4 6 8 10 8 6 4 21 2 3 4 5 6 7 8 92 10 21 11 202 10 169696969 4204204201 202 10 210 151 192 2 21000000000 11 3
2 2 -1 6969697 15 1000000000
In the first testcase, it is optimal to select $$$p=2$$$. Each attack, the first enemy takes $$$5-|2-1|=4$$$ damage, the second enemy takes $$$5$$$ damage, the third enemy takes $$$4$$$ damage, the fourth enemy takes $$$3$$$ damage, and the fifth enemy takes $$$2$$$ damage. After $$$2$$$ attacks, the first three enemies will be defeated. It can be shown that it is impossible to defeat $$$3$$$ enemies in less than $$$2$$$ attacks, no matter which $$$p$$$ is selected.
In the second testcase, we must kill all $$$9$$$ enemies. By selecting $$$p=5$$$, all nine enemies will be defeated in $$$2$$$ attacks.
In the third testcase, we must kill both enemies. However, it can be shown that no $$$p$$$ selected will damage both enemies at the same time, so the answer is $$$-1$$$.
In the fourth testcase, selecting $$$p=1$$$ will enable us to defeat the first enemy in $$$6969697$$$ attacks.
In the fifth testcase, selecting $$$p=10$$$ will make each enemy take $$$1$$$ damage per attack. Both enemies will be defeated in $$$15$$$ attacks.