算法练习专栏——Codeforces——Codeforces Round 939 (Div. 2)

A. Nene’s Game

原题

Nene invented a new game based on an increasing sequence of integers $a_1, a_2, \ldots, a_k$.

In this game, initially $n$ players are lined up in a row. In each of the rounds of this game, the following happens:

• Nene finds the $a_1$-th, $a_2$-th, $\ldots$, $a_k$-th players in a row. They are kicked out of the game simultaneously. If the $i$-th player in a row should be kicked out, but there are fewer than $i$ players in a row, they are skipped.

Once no one is kicked out of the game in some round, all the players that are still in the game are declared as winners.

For example, consider the game with $a=[3, 5]$ and $n=5$ players. Let the players be named player A, player B, $\ldots$, player E in the order they are lined up initially. Then,

• Before the first round, players are lined up as ABCDE. Nene finds the $3$-rd and the $5$-th players in a row. These are players C and E. They are kicked out in the first round.
• Now players are lined up as ABD. Nene finds the $3$-rd and the $5$-th players in a row. The $3$-rd player is player D and there is no $5$-th player in a row. Thus, only player D is kicked out in the second round.
• In the third round, no one is kicked out of the game, so the game ends after this round.
• Players A and B are declared as the winners.

Nene has not yet decided how many people would join the game initially. Nene gave you $q$ integers $n_1, n_2, \ldots, n_q$ and you should answer the following question for each $1 \le i \le q$ independently:

• How many people would be declared as winners if there are $n_i$ players in the game initially?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 250$). The description of test cases follows.

The first line case contains two integers $k$ and $q$ ($1 \le k, q \le 100$) — the length of the sequence $a$ and the number of values $n_i$ you should solve this problem for.

The second line contains $k$ integers $a_1,a_2,\ldots,a_k$ ($1\leq a_1<a_2<\ldots<a_k\leq 100$) — the sequence $a$.

The third line contains $q$ integers $n_1,n_2,\ldots,n_q$ ($1\leq n_i \leq 100$).

Output

For each test case, output $q$ integers: the $i$-th ($1\le i \le q$) of them should be the number of players declared as winners if initially $n_i$ players join the game.

Example

input

6
2 1
3 5
5
5 3
2 4 6 7 9
1 3 5
5 4
3 4 5 6 7
1 2 3 4
2 3
69 96
1 10 100
1 1
100
50
3 3
10 20 30
1 10 100

output

2 
1 1 1 
1 2 2 2 
1 10 68 
50 
1 9 9 

Note

The first test case was explained in the statement.

In the second test case, when $n=1$, the only player stays in the game in the first round. After that, the game ends and the only player is declared as a winner.

翻译

Nene 发明了一种基于整数递增序列的新游戏 $a _ 1, a _ 2, \ldots, a _ k$ 。

在这个游戏中，最初 $n$ 玩家排成一排。在本游戏的每一轮中，都会发生以下情况：

• Nene 找到连续第 $a _ 1$ 、第 $a _ 2$ 、第 $\ldots$ 、第 $a _ k$ 个玩家。他们同时被踢出游戏。如果连续第 $i$ 个玩家应被踢出，但连续玩家少于 $i$ 个，则他们会被跳过。

一旦在某一轮中没有人被踢出游戏，所有仍在游戏中的玩家都将被宣布为获胜者。

例如，考虑玩家为 $a=[3, 5]$ 和 $n=5$ 的游戏。让玩家按照最初排列的顺序命名为玩家 A、玩家 B、 $\ldots$ 、玩家 E。然后，

• 第一轮开始前，玩家按ABCDE排列。 Nene 找到连续第 $3$ -rd 和第 $5$ -th 玩家。他们是选手 C 和 E。他们在第一轮就被淘汰了。
• 现在玩家排列为ABD。 Nene 找到连续第 $3$ -rd 和第 $5$ -th 玩家。第 $3$ -rd 个玩家是玩家 D，并且连续没有第 $5$ -th 个玩家。因此，第二轮中只有玩家 D 被踢出局。
• 在第三轮中，没有人被踢出游戏，因此本轮后游戏结束。
• 玩家 A 和 B 被宣布为获胜者。

Nene 尚未决定最初有多少人加入游戏。 Nene 为您提供了 $q$ 整数 $n _ 1, n _ 2, \ldots, n _ q$ ，您应该针对每个 $1 \le i \le q$ 独立回答以下问题：

• 如果游戏最初有 $n _ i$ 名玩家，那么有多少人会被宣布为获胜者？

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 250$ )。测试用例的描述如下。

第一行 case 包含两个整数 $k$ 和 $q$ ( $1 \le k, q \le 100$ ) - 序列 $a$ 的长度以及您应该解决此问题的值的数量 $n _ i$ 。

第二行包含 $k$ 整数 $a _ 1,a _ 2,\ldots,a _ k$ ( $1\leq a _ 1<a _ 2<\ldots<a _ k\leq 100$ ) - 序列 $a$ 。

第三行包含 $q$ 整数 $n _ 1,n _ 2,\ldots,n _ q$ ( $1\leq n _ i \leq 100$ )。

输出

对于每个测试用例，输出 $q$ 个整数：如果最初有 $n _ i$ 个玩家加入游戏，则其中的第 $i$ 个( $1\le i \le q$ )应该是宣布为获胜者的玩家数量。

Example

input

6
2 1
3 5
5
5 3
2 4 6 7 9
1 3 5
5 4
3 4 5 6 7
1 2 3 4
2 3
69 96
1 10 100
1 1
100
50
3 3
10 20 30
1 10 100

output

2 
1 1 1 
1 2 2 2 
1 10 68 
50 
1 9 9 

思路

​ 稍微手玩一下就可以知道这么一个结论了:对于这些序列中比最小值大的所有数字的选手绝对都会被淘汰,比它小的全部胜利.

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 110;
int k, q;
int a[N];

void solve() {
    cin >> k >> q;
    int minb = INF;
    fore (i, 1, k){
        int x;
        cin >> x;
        minb = min(minb, x);
    }
    fore (i, 1, q) {
        int x;
        cin >> x;
        cout << (x < minb ? x : minb - 1) << " \n"[i == q];
    }
}
// 2 5
// 1 2 3 4 5 6 7 8 9 10
// 1 3 4 5 6 7 8 9 10
// 1 4 5 7 8 9 10
// 1 5 7 

int main()
{
    
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    return 0;
}

B. Nene and the Card Game

原题

You and Nene are playing a card game. The deck with $2n$ cards is used to play this game. Each card has an integer from $1$ to $n$ on it, and each of integers $1$ through $n$ appears exactly on $2$ cards. Additionally, there is a table where cards are placed during the game (initially, the table is empty).

In the beginning of the game, these $2n$ cards are distributed between you and Nene so that each player receives $n$ cards.

After it, you and Nene alternatively take $2n$ turns, i.e. each person takes $n$ turns, starting with you. On each turn:

• The player whose turn is it selects one of the cards in his hand. Let $x$ be the number on it.
• The player whose turn is it receives $1$ point if there is already a card with the integer $x$ on the table (otherwise, he receives no points). After it, he places the selected card with the integer $x$ on the table.

Note that turns are made publicly: each player can see all the cards on the table at each moment.

Nene is very smart so she always selects cards optimally in order to maximize her score in the end of the game (after $2n$ rounds). If she has several optimal moves, she selects the move that minimizes your score in the end of the game.

More formally, Nene always takes turns optimally in order to maximize her score in the end of the game in the first place and to minimize your score in the end of the game in the second place.

Assuming that the cards are already distributed and cards in your hand have integers $a_1, a_2, \ldots, a_n$ written on them, what is the maximum number of points you can get by taking your turns optimally?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of test cases follows.

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of cards you and Nene receive in the beginning of the game.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the integers on the cards in your hand. It is guaranteed that each integer from $1$ through $n$ appears in the sequence $a_1, a_2, \ldots, a_n$ at most $2$ times.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output one integer: the maximum number of points you can get.

Example

input

5
4
1 1 2 3
8
7 4 1 2 8 8 5 5
8
7 1 4 5 3 4 2 6
3
1 2 3
1
1

output

1
2
1
0
0

Note

In the first test case, the integers written on your cards are $1$, $1$, $2$ and $3$. The integers written on Nene’s cards are $2$, $3$, $4$ and $4$. The game may proceed as follows:

1. You select one of the cards with an integer $1$ written on it and place it on the table.
2. Nene selects one of the cards with an integer $4$ written on it and places it on the table.
3. You select the card with an integer $1$ written on it, receive $1$ point, and place the selected card on the table.
4. Nene selects the card with an integer $4$ written on it, receive $1$ point, and places the selected card on the table.
5. You select the card with an integer $2$ written on it and place it on the table.
6. Nene selects the card with an integer $2$ written on it, receive $1$ point, and places the selected card on the table.
7. You select the card with an integer $3$ written on it and place it on the table.
8. Nene selects the card with an integer $3$ written on it, receive $1$ point, and places the selected card on the table.

At the end of the game, you scored $1$ point, and Nene scored $3$. It can be shown that you cannot score more than $1$ point if Nene plays optimally, so the answer is $1$.

In the second test case, if both players play optimally, you score $2$ points and Nene scores $6$ points.

翻译

你和 Nene 正在玩纸牌游戏。使用带有 $2n$ 卡的牌组来玩此游戏。每张卡片上都有一个从 $1$ 到 $n$ 的整数，并且每个整数 $1$ 到 $n$ 都准确地出现在 $2$ 卡上。此外，还有一张桌子，用于在游戏过程中放置纸牌(最初，桌子是空的)。

在游戏开始时，这些 $2n$ 卡牌会在您和 Nene 之间分发，以便每个玩家都会收到 $n$ 卡牌。

之后，你和 Nene 交替进行 $2n$ 轮，即每个人进行 $n$ 轮，从你开始。每回合：

• 轮到的玩家选择他手中的一张牌。让 $x$ 成为上面的数字。
• 如果桌上已经有一张整数为 $x$ 的牌，轮到的玩家将获得 $1$ 分(否则，他不会获得任何分数)。之后，他将所选的带有整数 $x$ 的卡片放在桌子上。

请注意，回合是公开进行的：每个玩家在每个时刻都可以看到桌上的所有牌。

Nene 非常聪明，所以她总是选择最佳的牌，以便在游戏结束时( $2n$ 轮后)最大化她的分数。如果她有几个最佳动作，她会选择在游戏结束时使你的分数最小化的动作。

更正式地说，内内总是以最佳方式轮流，以便首先在游戏结束时最大化她的得分，然后在游戏结束时最小化你的得分。

假设卡片已经分发完毕，并且你手中的卡片上写有整数 $a _ 1, a _ 2, \ldots, a _ n$ ，那么最优轮流最多可以获得多少分？

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 10^4$ )。测试用例的描述如下。

第一行包含一个整数 $n$ ( $1 \le n \le 2 \cdot 10^5$ ) - 您和 Nene 在游戏开始时收到的牌数。

第二行包含 $n$ 整数 $a _ 1, a _ 2, \ldots, a _ n$ ( $1 \le a _ i \le n$ ) - 您手中的牌上的整数。保证从 $1$ 到 $n$ 的每个整数最多出现在序列 $a _ 1, a _ 2, \ldots, a _ n$ 中 $2$ 次。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。

输出

对于每个测试用例，输出一个整数：可以获得的最大分数。

Example

input

5
4
1 1 2 3
8
7 4 1 2 8 8 5 5
8
7 1 4 5 3 4 2 6
3
1 2 3
1
1

output

1
2
1
0
0

笔记

在第一个测试用例中，卡上写入的整数是 $1$ 、 $1$ 、 $2$ 和 $3$ 。 Nene 卡片上写的整数是 $2$ 、 $3$ 、 $4$ 和 $4$ 。游戏可能会按如下方式进行：

1. 选择一张写有整数 $1$ 的卡片并将其放在桌子上。
2. Nene 选择一张写有整数 $4$ 的卡片并将其放在桌子上。
3. 您选择写有整数 $1$ 的卡片，获得 $1$ 点，并将所选卡片放在桌子上。
4. Nene选择写有整数 $4$ 的卡片，获得 $1$ 点，并将所选卡片放在桌子上。
5. 选择写有整数 $2$ 的卡片并将其放在桌子上。
6. Nene选择写有整数 $2$ 的卡片，获得 $1$ 点，并将所选卡片放在桌子上。
7. 选择写有整数 $3$ 的卡片并将其放在桌子上。
8. Nene 选择写有整数 $3$ 的卡片，获得 $1$ 点，并将所选卡片放在桌子上。

比赛结束时，您获得了 $1$ 分，内内获得了 $3$ 分。可以证明，如果 Nene 发挥最佳，您的得分不能超过 $1$ 分，因此答案是 $1$ 。

在第二个测试用例中，如果两名玩家都发挥最佳，您将获得 $2$ 分，Nene 将获得 $6$ 分。

思路

​

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define refore(i, l, r) for(int i = (int)(l); i >= r; i--)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 2e5 + 10;
int n;
int a[N];
int st[N];
int b[N];

void solve() {
    me0(st);
    int ans = 0, k = -1;
    cin >> n;
    fore (i, 1, n) {
        cin >> a[i];
        st[a[i]] ++;
        if (st[a[i]] == 2) ans ++;
    }

    // int kk = 0;
    // fore (i, 1, n) {
    //     if (!st[i]) b[++kk] = i;
    // }
    // int kkk = 0;
    // sort (a + 1, a + n + 1);
    // fore (i, 1, n) {
    //     if (st[a[i]] == 1) st[a[i]] ++;
    //     else {
    //         if (kkk < kk) st[b[++kkk]] ++;
    //         else {
    //             ans += n - i + 1;
    //             break;
    //         }
    //     }
    // }

    cout << ans << ed;
}


int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    return 0;
}

C. Nene’s Magical Matrix

The magical girl Nene has an $n\times n$ matrix $a$ filled with zeroes. The $j$-th element of the $i$-th row of matrix $a$ is denoted as $a_{i, j}$.

She can perform operations of the following two types with this matrix:

• Type $1$ operation: choose an integer $i$ between $1$ and $n$ and a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$. Assign $a_{i, j}:=p_j$ for all $1 \le j \le n$ simultaneously.
• Type $2$ operation: choose an integer $i$ between $1$ and $n$ and a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$. Assign $a_{j, i}:=p_j$ for all $1 \le j \le n$ simultaneously.

Nene wants to maximize the sum of all the numbers in the matrix $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$. She asks you to find the way to perform the operations so that this sum is maximized. As she doesn’t want to make too many operations, you should provide a solution with no more than $2n$ operations.

A permutation of length $n$ is an array consisting 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 in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of test cases follows.

The only line of each test case contains a single integer $n$ ($1 \le n \le 500$) — the size of the matrix $a$.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, in the first line output two integers $s$ and $m$ ($0\leq m\leq 2n$) — the maximum sum of the numbers in the matrix and the number of operations in your solution.

In the $k$-th of the next $m$ lines output the description of the $k$-th operation:

• an integer $c$ ($c \in {1, 2}$) — the type of the $k$-th operation;
• an integer $i$ ($1 \le i \le n$) — the row or the column the $k$-th operation is applied to;
• a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ — the permutation used in the $k$-th operation.

Note that you don’t need to minimize the number of operations used, you only should use no more than $2n$ operations. It can be shown that the maximum possible sum can always be obtained in no more than $2n$ operations.

Example

input

2
1
2

output

1 1
1 1 1
7 3
1 1 1 2
1 2 1 2
2 1 1 2

Note

In the first test case, the maximum sum $s=1$ can be obtained in $1$ operation by setting $a_{1, 1}:=1$.

In the second test case, the maximum sum $s=7$ can be obtained in $3$ operations as follows:

It can be shown that it is impossible to make the sum of the numbers in the matrix larger than $7$.

翻译

魔法少女妮妮有一个充满零的 $n\times n$ 矩阵 $a$ 。矩阵 $a$ 的第 $i$ 行的第 $j$ 个元素表示为 $a _ {i, j}$ 。

她可以用这个矩阵进行以下两种类型的运算：

• 输入 $1$ 运算：选择 $1$ 和 $n$ 之间的整数 $i$ 以及 $1$ 到 $n$ 之间的整数排列 $p _ 1, p _ 2, \ldots, p _ n$ 。同时为所有 $1 \le j \le n$ 分配 $a _ {i, j}:=p _ j$ 。
• 输入 $2$ 运算：选择 $1$ 和 $n$ 之间的整数 $i$ 以及从 $1$ 到 $n$ 的整数排列 $p _ 1, p _ 2, \ldots, p _ n$ 。同时为所有 $1 \le j \le n$ 分配 $a _ {j, i}:=p _ j$ 。

Nene 想要最大化矩阵 $\sum\limits _ {i=1}^{n}\sum\limits _ {j=1}^{n}a _ {i,j}$ 中所有数字的总和。她要求你找到执行运算的方法，以使这个总和最大化。由于她不想进行太多操作，因此您应该提供不超过 $2n$ 操作的解决方案。

长度为 $n$ 的排列是一个由 $n$ 个从 $1$ 到 $n$ 的不同整数以任意顺序组成的数组。例如， $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列( $2$ 在数组中出现了两次)，而 $[1,3,4]$ 也不是一个排列( $n=3$ 但数组中有 $4$ )大批）。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 500$ )。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $n$ ( $1 \le n \le 500$ ) - 矩阵 $a$ 的大小。

保证所有测试用例的 $n^2$ 之和不超过 $5 \cdot 10^5$ 。

输出

对于每个测试用例，第一行输出两个整数 $s$ 和 $m$ ( $0\leq m\leq 2n$ ) - 矩阵中的数字与解决方案中的运算数的最大总和。

在接下来的 $m$ 行的第 $k$ -th 行中，输出第 $k$ -th 操作的描述：

• 整数 $c$ ( $c \in \{1, 2\}$ ) - 第 $k$ 个操作的类型；
• 整数 $i$ ( $1 \le i \le n$ ) - 第 $k$ 个运算应用到的行或列；
• 从 $1$ 到 $n$ 的整数排列 $p _ 1, p _ 2, \ldots, p _ n$ - 第 $k$ 个运算中使用的排列。

请注意，您不需要最小化所使用的操作数量，只需使用不超过 $2n$ 操作即可。可以证明，总能在不超过 $2n$ 次操作中获得最大可能的总和。

Example

input

2
1
2

output

1 1
1 1 1
7 3
1 1 1 2
1 2 1 2
2 1 1 2

思路

​

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define refore(i, l, r) for(int i = (int)(l); i >= r; i--)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 2e5 + 10;
int n;
int a[N];
int st[N];
int b[N];

void solve() {
    int n, ans = 0;
    cin >> n;
    fore (i, 1, n) {
        fore (j, 1, n) {
            ans += max(j, n - i + 1);
        }
    }

    cout << ans << " " << 2 * n << ed;

    refore (i, n, 1) {
        cout << "2" << " " << i << " ";
        refore (j, n, 1) {
            cout << j << " ";
        }

        cout << "1" << " " << n - i + 1 << " ";

        fore (j, 1, n) {
            cout << j << " ";
        }
        cout << ed;
    }

}

int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    return 0;
}

D. Nene and the Mex Operator

Nene gave you an array of integers $a_1, a_2, \ldots, a_n$ of length $n$.

You can perform the following operation no more than $5\cdot 10^5$ times (possibly zero):

• Choose two integers $l$ and $r$ such that $1 \le l \le r \le n$, compute $x$ as $\operatorname{MEX}({a_l, a_{l+1}, \ldots, a_r})$, and simultaneously set $a_l:=x, a_{l+1}:=x, \ldots, a_r:=x$.

Here, $\operatorname{MEX}$ of a set of integers ${c_1, c_2, \ldots, c_k}$ is defined as the smallest non-negative integer $m$ which does not occur in the set $c$.

Your goal is to maximize the sum of the elements of the array $a$. Find the maximum sum and construct a sequence of operations that achieves this sum. Note that you don’t need to minimize the number of operations in this sequence, you only should use no more than $5\cdot 10^5$ operations in your solution.

Input

The first line contains an integer $n$ ($1 \le n \le 18$) — the length of the array $a$.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0\leq a_i \leq 10^7$) — the array $a$.

Output

In the first line, output two integers $s$ and $m$ ($0\le m\le 5\cdot 10^5$) — the maximum sum of elements of the array $a$ and the number of operations in your solution.

In the $i$-th of the following $m$ lines, output two integers $l$ and $r$ ($1 \le l \le r \le n$), representing the parameters of the $i$-th operation.

It can be shown that the maximum sum of elements of the array $a$ can always be obtained in no more than $5 \cdot 10^5$ operations.

Examples

input

2
0 1

output

4 1
1 2

input

3
1 3 9

output

13 0

input

4
1 100 2 1

output

105 2
3 3
3 4

input

1
0

output

1 1
1 1

翻译

Nene 给了你一个长度为 $n$ 的整数数组 $a _ 1, a _ 2, \ldots, a _ n$ 。

您可以执行以下操作不超过 $5\cdot 10^5$ 次(可能为零)：

• 选择两个整数 $l$ 和 $r$ ，使得 $1 \le l \le r \le n$ ，将 $x$ 计算为 $\operatorname{MEX}(\{a _ l, a _ {l+1}, \ldots, a _ r\})$ ，并同时设置 $a _ l:=x, a _ {l+1}:=x, \ldots, a _ r:=x$ 。

这里，整数集合 $\{c _ 1, c _ 2, \ldots, c _ k\}$ 中的 $\operatorname{MEX}$ 被定义为集合{77557664}中不出现的最小非负整数 $m$ 。

您的目标是最大化数组 $a$ 的元素之和。找到最大总和并构建实现该总和的操作序列。请注意，您不需要最大限度地减少此序列中的操作数量，只需在解决方案中使用不超过 $5\cdot 10^5$ 操作即可。

输入

第一行包含一个整数 $n$ ( $1 \le n \le 18$ ) - 数组 $a$ 的长度。

第二行包含 $n$ 整数 $a _ 1,a _ 2,\ldots,a _ n$ ( $0\leq a _ i \leq 10^7$ ) - 数组 $a$ 。

输出

在第一行中，输出两个整数 $s$ 和 $m$ ( $0\le m\le 5\cdot 10^5$ ) - 数组 $a$ 的元素的最大总和以及解决方案中的操作数。

在接下来的 $m$ 行的第 $i$ 行中，输出两个整数 $l$ 和 $r$ （ $1 \le l \le r \le n$ ），代表第 $i$ 操作的参数。

可以证明，数组 $a$ 的最大元素总和总是可以通过不超过 $5 \cdot 10^5$ 操作获得。

Examples

input

2
0 1

output

4 1
1 2

input

3
1 3 9

output

13 0

input

4
1 100 2 1

output

105 2
3 3
3 4

input

1
0

output

1 1
1 1

笔记

在第一个示例中，在使用 $l=1$ 和 $r=2$ 进行运算后，数组 $a$ 变为等于 $[2,2]$ 。可以证明，不可能获得更大的 $a$ 元素之和，所以答案是 $4$ 。

在第二个示例中，元素的初始总和是 $13$ ，可以证明它是最大的。

在第三个示例中，数组 $a$ 更改如下：

• 第一个操作（ $l=3$ ， $r=3$ ）之后，数组 $a$ 变得等于 $[1,100,0,1]$ ；
• 第二次操作（ $l=3$ 、 $r=4$ ）之后，数组 $a$ 变为等于 $[1,100,2,2]$ 。

可以证明，不可能获得更大的 $a$ 元素之和，所以答案是 $105$ 。

思路

​ 持续更新中……

代码

// 持续更新中....

E1. Nene vs. Monsters (Easy Version)

原题

This is the easy version of the problem. The only difference between the versions is the constraints on $a_i$. You can make hacks only if both versions of the problem are solved.

Nene is fighting with $n$ monsters, located in a circle. These monsters are numbered from $1$ to $n$, and the $i$-th ($1 \le i \le n$) monster’s current energy level is $a_i$.

Since the monsters are too strong, Nene decided to fight with them using the Attack Your Neighbour spell. When Nene uses this spell, the following actions happen in the following order one by one:

• The $1$-st monster attacks the $2$-nd monster;
• The $2$-nd monster attacks the $3$-rd monster;
• $\ldots$
• The $(n-1)$-th monster attacks the $n$-th monster;
• The $n$-th monster attacks the $1$-st monster.

When the monster with energy level $x$ attacks the monster with the energy level $y$, the energy level of the defending monster becomes $\max(0, y-x)$ (the energy level of the attacking monster remains equal to $x$).

Nene is going to use this spell $10^{100}$ times and deal with the monsters that will still have a non-zero energy level herself. She wants you to determine which monsters will have a non-zero energy level once she will use the described spell $10^{100}$ times.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of test cases follows.

The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of monsters.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 2 \cdot 10^5$) — the current energy levels of monsters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case,

• in the first line output an integer $m$ — the number of monsters with non-zero energy level after $10^{100}$ uses of the spell;
• in the second line of output $m$ integers $i_1,i_2,\ldots,i_m$ ($1 \le i_1 < i_2 < \ldots < i_m \le n$) — the indices of these monsters in the increasing order.

If $m=0$, you may either output an empty line or don’t output it.

Example

input

5
3
2 5 3
2


0 0
4
1 5 7 2
4
4 2 1 2
13
1 1 4 5 1 4 1 9 1 9 8 1 0

output

1
1 
0

1
1 
2
1 3 
6
1 3 6 8 10 12 

Note

In the first test case, the following actions happen during the first $3$ uses of the spell in this order:

• Nene uses the Attack Your Neighbour spell for the first time;
• the $1$-st monster attacks the $2$-nd monster, after the attack the energy level of the $2$-nd monster becomes equal to $\max(0, 5-2)=3$;
• the $2$-nd monster attacks the $3$-rd monster, after the attack the energy level of the $3$-rd monster becomes equal to $\max(0, 3-3)=0$;
• the $3$-rd monster attacks the $1$-st monster, after the attack the energy level of the $1$-st monster becomes equal to $\max(0, 2-0)=2$;
• Nene uses the Attack Your Neighbour spell for the second time;
• the $1$-st monster attacks the $2$-nd monster, after the attack the energy level of the $2$-nd monster becomes equal to $\max(0, 3-2)=1$;
• the $2$-nd monster attacks the $3$-rd monster, after the attack the energy level of the $3$-rd monster becomes equal to $\max(0, 0-1)=0$;
• the $3$-rd monster attacks the $1$-st monster, after the attack the energy level of the $1$-st monster becomes equal to $\max(0, 2-0)=2$;
• Nene uses the Attack Your Neighbour spell for the third time;
• the $1$-st monster attacks the $2$-nd monster, after the attack the energy level of the $2$-nd monster becomes equal to $\max(0, 1-2)=0$;
• the $2$-nd monster attacks the $3$-rd monster, after the attack the energy level of the $3$-rd monster becomes equal to $\max(0, 0-0)=0$;
• the $3$-rd monster attacks the $1$-st monster, after the attack the energy level of the $1$-st monster becomes equal to $\max(0, 2-0)=2$.

After each of the next uses of the spell, energy levels of monsters do not change. Thus, only the $1$-st monster has a non-zero energy level in the end.

In the second test case, both monsters initially have zero energy level.

翻译

这是问题的简单版本。版本之间的唯一区别是对 $a _ i$ 的限制。只有当问题的两个版本都得到解决时，你才能进行黑客攻击。

Nene 正在与围成一圈的 $n$ 怪物战斗。这些怪物的编号为 $1$ 到 $n$ ，第 $i$ ( $1 \le i \le n$ )只怪物的当前能量等级为 $a _ i$ 。

由于怪物太强大，妮妮决定使用“攻击你的邻居”法术与它们战斗。当内内使用此法术时，以下动作将按以下顺序一一发生：

• 第 $1$ 个怪物攻击第 $2$ 个怪物；
• $2$ -rd 怪物攻击 $3$ -rd 怪物；
• $\ldots$
• 第 $(n-1)$ 个怪物攻击第 $n$ 个怪物；
• 第 $n$ 个怪物攻击第 $1$ 个怪物。

当能量等级为 $x$ 的怪物攻击能量等级为 $y$ 的怪物时，防御怪物的能量等级变为 $\max(0, y-x)$ (攻击怪物的能量等级保持等于 $x$ )。

Nene 将使用此法术 $10^{100}$ 次并处理那些她自己仍具有非零能量水平的怪物。她希望你确定一旦她使用所描述的咒语 $10^{100}$ 次，哪些怪物将具有非零能量水平。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 10^4$ )。测试用例的描述如下。

第一行包含一个整数 $n$ ( $2 \le n \le 2 \cdot 10^5$ ) - 怪物的数量。

第二行包含 $n$ 整数 $a _ 1, a _ 2, \ldots, a _ n$ ( $0 \le a _ i \le 2 \cdot 10^5$ ) - 怪物的当前能量级别。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。

输出

对于每个测试用例，

• 在第一行中输出一个整数 $m$ ——在 $10^{100}$ 使用该法术后具有非零能量水平的怪物数量；
• 在输出的第二行 $m$ 整数 $i _ 1,i _ 2,\ldots,i _ m$ ( $1 \le i _ 1 < i _ 2 < \ldots < i _ m \le n$ ) - 这些怪物的索引，按升序排列。

如果是 $m=0$ ，则可以输出空行，也可以不输出。

Example

input

5
3
2 5 3
2
0 0
4
1 5 7 2
4
4 2 1 2
13
1 1 4 5 1 4 1 9 1 9 8 1 0

output

1
1 
0

1
1 
2
1 3 
6
1 3 6 8 10 12 

笔记

在第一个测试用例中，在第一次 $3$ 使用该咒语期间会按以下顺序发生以下操作：

• 内内第一次使用攻击你的邻居法术；
• 第 $1$ 个怪物攻击第 $2$ 个怪物，攻击后第 $2$ 个怪物的能量等级变为 $\max(0, 5-2)=3$ ；
• $2$ -rd 怪兽攻击 $3$ -rd 怪兽，攻击后， $3$ -rd 怪兽的能量值变为等于 $\max(0, 3-3)=0$ ；
• $3$ -rd怪物攻击 $1$ -st怪物，攻击后 $1$ -st怪物的能量等级变为等于 $\max(0, 2-0)=2$ ；
• 内内第二次使用“攻击你的邻居”法术；
• 第 $1$ 个怪物攻击第 $2$ 个怪物，攻击后第 $2$ 个怪物的能量等级变为等于 $\max(0, 3-2)=1$ ；
• $2$ -rd 怪兽攻击 $3$ -rd 怪兽，攻击后 $3$ -rd 怪兽的能量值变为等于 $\max(0, 0-1)=0$ ；
• $3$ -rd怪物攻击 $1$ -st怪物，攻击后 $1$ -st怪物的能量等级变为等于 $\max(0, 2-0)=2$ ；
• 内内第三次使用“攻击你的邻居”法术；
• 第 $1$ 个怪物攻击第 $2$ 个怪物，攻击后第 $2$ 个怪物的能量等级变为等于 $\max(0, 1-2)=0$ ；
• $2$ -rd 怪物攻击 $3$ -rd 怪物，攻击后， $3$ -rd 怪物的能量等级变为等于 $\max(0, 0-0)=0$ ；
• $3$ -rd 怪兽攻击 $1$ -st 怪兽，攻击后 $1$ -st 怪兽的能量等级变为 $\max(0, 2-0)=2$ 。

在下次使用该法术后，怪物的能量水平不会改变。因此，只有 $1$ -st 怪物最终具有非零能量水平。

在第二个测试用例中，两个怪物最初的能量水平为零。

思路

​ 手玩一下可以发现整个序列很快就会断成一段一段的（中间有 0 分隔的）序列。原因就是如果第一个数前面是 0 00，这个数每轮都会稳定给后面减去能量值，如果第二个数能坚持住，那么它的能量值应该是比较多的，那么第三个数就惨了，它需要一直承受来自第二个数的摧残，导致它很快就会归零。

​ 算一下第三个数最久能坚持多久。那么我们肯定让第一二个数尽可能的小，假设坚持了 t tt 轮，那么第一个数就是 1 11，第二个数就是 t，那么第三个数受到的总伤害就是$t - 1 + t - 2 + t - 3 + … + 0 = \frac{t * (t - 1) }{2} $,第三个数就完蛋了,第3个数就是$t^2$级别的.可以预料到如果还有数的话,其承受的伤害肯也是阶梯式上升的,比如第4个是$t^3$级别的等等.

​ 因为序列中每个数也就是$2*10^5$,所以它最多撑不过200轮,直接暴力枚举这么多轮次就可以了,最后我们形成的序列就是1个或者2个怪挨在一起的情况,我们需要做的就是计算1个和2个怪的组数之和.

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define refore(i, l, r) for(int i = (int)(l); i >= r; i--)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 2e5 + 10;
int n;
int a[N];
int st[N];
int b[N];

void solve() {
    cin >> n;
    for(int i = 0;i < n; i++)cin >> a[i];
    2 * 10 ^ 5

    // 现在直接跑400 ~ 500轮左右即可
    for(int rd = 1;rd <= 1000; rd++){
        for(int i = 0;i < n; i++){
            a[(i + 1) % n] = max(0, a[(i + 1) % n] - a[i]);
        }
    }

    for(int i = 0;i < n; i++){
        if(a[i] > 0 && a[(i + 1) % n] > 0){
            a[(i + 1) % n] = 0;
        }
    }
            
    vector<int> ans;
    for(int i = 0;i < n; i++)
        if(a[i] > 0)
            ans.push_back(i + 1);
    cout << ans.size() << endl;
    for(auto x : ans)
        cout << x << " ";
    cout << ed;
}

int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    return 0;
}