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

A. Chess For Three

原题

Three friends gathered to play a few games of chess together.

In every game, two of them play against each other. The winner gets $2$ points while the loser gets $0$, and in case of a draw, both players get $1$ point each. Note that the same pair of players could have played any non-negative number of times (possibly zero). It is also possible that no games were played at all.

You’ve been told that their scores after all the games were played were $p_1$, $p_2$ and $p_3$. Additionally, it is guaranteed that $p_1 \leq p_2 \leq p_3$ holds.

Find the maximum number of draws that could have happened and print it. If there isn’t any way to obtain $p_1$, $p_2$ and $p_3$ as a result of a non-negative number of games between the three players, print $-1$ instead.

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 the test cases follows.

The first line of each test case contains three integers $p_1$, $p_2$ and $p_3$ ($0 \leq p_1 \leq p_2 \leq p_3 \leq 30$) — the scores of the three players, sorted non-decreasingly.

Output

For each testcase, print one number — the maximum possible number of draws that could’ve happened, or $-1$ if the scores aren’t consistent with any valid set of games and results.

Example

input

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

output

1
2
3
4
5
6
7
0
1
-1
2
-1
6
2

Note

In the first example, no games were played at all, so no draws could occur either.

For the second example, exactly one game occurred between the second and the third player and it ended in draw, so the answer is $1$.

It’s easy to see that there’s no set of games achieving the scores in third example, so the answer for it is $-1$.

翻译

三个朋友聚在一起下几盘棋。

在每场比赛中，他们两人都会互相对抗。获胜者获得 $2$ 分，失败者获得 $0$ 分，如果平局，双方玩家各获得 $1$ 分。请注意，同一对玩家可以玩任意非负次数(可能为零)。也有可能根本没有玩任何游戏。

您被告知，所有比赛结束后他们的得分分别是 $p _ 1$ 、 $p _ 2$ 和 $p _ 3$ 。此外，还保证 $p _ 1 \leq p _ 2 \leq p _ 3$ 成立。

找出可能发生的最大抽奖次数并打印出来。如果由于三名玩家之间的游戏次数为非负数而无法获取 $p _ 1$ 、 $p _ 2$ 和 $p _ 3$ ，请改为打印 $-1$ 。

输入

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

每个测试用例的第一行包含三个整数 $p_1$ 、 $p_2$ 和 $p_3$ ( $0 \leq p_1 \leq p_2 \leq p_3 \leq 30$ ) - 三位玩家的分数，非降序排序。

输出

对于每个测试用例，打印一个数字 - 可能发生的最大可能平局次数，如果分数与任何有效的一组游戏和结果不一致，则打印 $-1$ 。

Example

input

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

output

1
2
3
4
5
6
7
0
1
-1
2
-1
6
2

笔记

在第一个示例中，根本没有进行任何比赛，因此也不会发生平局。

对于第二个示例，第二个和第三个玩家之间恰好发生了一场比赛，并且以平局结束，因此答案是 $1$ 。

很容易看出，没有一组游戏能够达到第三个示例中的分数，因此答案是 $-1$ 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#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 = 1e5 + 10;

void solve() {
    int p1, p2, p3;
    cin >> p1 >> p2 >> p3;
 
    if ((p1 + p2 + p3) % 2) {
      cout << "-1\n";
    }
    else {
 
      vector<int> cur = {p1, p2, p3};
      sort(cur.begin(), cur.end());
      int ans = 0;
      while (cur[1]) {
        ans++;
        cur[2]--;
        cur[1]--;
        sort(cur.begin(), cur.end());
      }
      cout << ans << ed;
    }
}
int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}

B. Cat, Fox and the Lonely Array

原题

Today, Cat and Fox found an array $a$ consisting of $n$ non-negative integers.

Define the loneliness of $a$ as the smallest positive integer $k$ ($1 \le k \le n$) such that for any two positive integers $i$ and $j$ ($1 \leq i, j \leq n - k +1$), the following holds:

$$
a_i | a_{i+1} | \ldots | a_{i+k-1} = a_j | a_{j+1} | \ldots | a_{j+k-1},
$$
where $x | y$ denotes the bitwise OR of $x$ and $y$. In other words, for every $k$ consecutive elements, their bitwise OR should be the same. Note that the loneliness of $a$ is well-defined, because for $k = n$ the condition is satisfied.

Cat and Fox want to know how lonely the array $a$ is. Help them calculate the loneliness of the found array.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4 $ ) — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \leq n \leq 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i < 2^{20}$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases doesn’t exceed $10^5$.

Output

For each test case, print one integer — the loneliness of the given array.

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
7
1
0
3
2 2 2
3
1 0 2
5
3 0 1 4 2
5
2 0 4 0 2
7
0 0 0 0 1 2 4
8
0 1 3 2 2 1 0 3

output

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

Note

In the first example, the loneliness of an array with a single element is always $1$, so the answer is $1$.

In the second example, the OR of each subarray of length $k = 1$ is $2$, so the loneliness of the whole array is $1$.

In the seventh example, it’s true that $(0 | 1 | 3) = (1 | 3 | 2) = (3 | 2 | 2) = (2 | 2 | 1) = (2 | 1 | 0) = (1 | 0 | 3) = 3$, so the condition is satisfied for $k = 3$. We can verify that the condition is not true for any smaller $k$, so the answer is indeed $3$.

翻译

今天，Cat 和 Fox 发现了一个由 $n$ 非负整数组成的数组 $a$ 。

将 $a$ 的孤独度定义为 最小 正整数 $k$ ( $1 \le k \le n$ )，这样对于任意两个正整数 $i$ 和 $j$ ( $1 \leq i, j \leq n - k +1$ )，以下公式成立：

$$
a _ i | a _ {i+1} | \ldots | a _ {i+k-1} = a _ j | a _ {j+1} | \ldots | a _ {j+k-1},
$$
其中 $x | y$ 表示 $x$ 和 $y$ 的按位 OR。换句话说，对于每个 $k$ 连续元素，它们的按位或应该相同。请注意， $a$ 的孤独性是明确定义的，因为对于 $k = n$ 满足条件。

猫和狐狸想知道数组 $a$ 有多孤独。帮助他们计算找到的数组的孤独度。

输入

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

每个测试用例的第一行包含一个整数 $n$ ( $1 \leq n \leq 10^5$ ) - 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 整数 $a _ 1, a _ 2, \ldots, a _ n$ ( $0 \leq a _ i < 2^{20}$ ) - 数组的元素。

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

输出

对于每个测试用例，打印一个整数——给定数组的孤独度。

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
7
1
0
3
2 2 2
3
1 0 2
5
3 0 1 4 2
5
2 0 4 0 2
7
0 0 0 0 1 2 4
8
0 1 3 2 2 1 0 3

output

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

思路

​ 这道题目主要是利用了**|** 操作的性质来写的,| 这个操作有着只要一段区间中存在着一个1,那么这段区间的对应的某一位就是1.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/**
                                                                                   .@@
                                                                                  .@@@@
                                                     :--:::::::-----==:           %%@@@%
                                             :*++*+==--========----------:-==:    @%@@@@.
                                        .:. ..-=+=+*+==---=----------------------:*@%@@@@         .:..
                                    .::::-----==+++====+***#+----=------:--------:-=%%@@@#+%@@@@@@@@@@@@@@@@@@@@@@@
                :+%@@@@@@@@@@@@@@%::::=*=+++++=++==*%*=-:=*#+##=-----------------:::-@%@@@@@@@@@@@@@@@@@@@@@@@@@@@*
             %%%%%%%%%%%%@@@@@@= .:=%@@@@@%#+=+++%@@@%+-==--++-=*=-------------:-----:*@@@@@@@@@@@@@@@@@@@@@@@@@@%
             .@%%%%%%%%%@@@@%-  .-+%@@@%@%%%####%#*#%%%%==----+=:-++-::------=----:::-:=@@@@@@@@@@@@@@@@@@@@@@@@%
               %%%%%%%%@%@@+  .::*%@@@@%#**#####******+*%+===---+=..:==---------:---::::-@@@@@@@@@@@@@@@@@@@@@@@
                %%%@%@%@@@:  .:.%%%%%#=+*+*+*#*+=+***+*#+##=--=-:-+.   ==--------::::--::-@@@@@@@@@@@@@@@@@@@@@
                .#%%%@%@%   . -@%%%*==+*++++**+++=+*++=++=+#--=----=:    +---:-::::::::--:-%@@@@@@@@@@@@@@@@@@=
                 :@%%%@=   . =%%%#---======+=========++=====*+--=-=--=.    --::::::::::::--=@@@@@@@@@@@@@@@@@@@:
                  @%@#   .  -%%*+---========-:===++======-==-==--=-----:     :-::::::::::::-=@@@@@@@@@@@@@@@@@@@=
                  @#.   .  .#*=+.-=-==-==-=-::===+=-==-=--=--==+=:------=     .-:::::::-:--:--#@@@@@@@@@@@@@@@@@@#
                 -         #+=-.:----=------.:-=-*===----==--==-+=-:::-::-:     :-::::::::::::==+@@@@@@@@@@@@@@@@@@
                     .    -==:..-=--==--:--:.-===+====----=====--=--::::::--      ::::::::::--:=%*=*@@@@@@@@@@@@@@@@.
                .+: .    .==-. :----==-::--:.---==-===---:------:----::::::-+       -:::------=--+#+#@@@@@@@@@@@@@@@@.
              .  . -    ::--. .::---:-:.-=-: :--==--==:=--:-::::::--=-:::-:::*.      :::-==-==--:--**@@@@@@@%@@@@@@@@@=
                :.:     :::.. .--:::::: --::.:-:---:--:--:::::::::--:==:::::::+.       -:-=-=------:*+@@@@@@@@+ #@@@@@@
               #-.     -::.. .=+:::::-:.--:-:.::::::::::+:::::::::::::=-:::::::=.       :=-=---------=%@@@@@@@@@  :@@@@
             =@-.     :=..   -=::::-:=.:::::-.::::::::::%.::::::::::::-=:::::::-+-        *%+=-------::%@@@@@@@@@:   :.
            #@*.      +-..  :-:::::::-..::::::.:::::::::%:-==:..::::::--+:::-:-====        :*%*+--------@@@@@@@@@@@
          .@@#       :=:   .::::::::-:.::::::-.::::::.::#.:-=-.:..::-.::-+:-=--===-=         -#++*+===-:#@@@@@@@@@@@@
         *@@*.    .  --.  .:::::::::-..::::.:::.::..:..-+:: :.......=-.::==--==-====-         .**++++++=*@@@@@@@@@@@@@@:
       =@@@==.   .: .=-.  ::::::.:::= .::::...::.-.....+::.  - :....:*::--==--=======-          -*++=+=++@@@@@@@@@@@@@@@@@@%-
     +@@@@::- . .:- :=-. .::::::.::=- .::......=.=.....+ :.  :  ... - -:-==+---==-=--*: .        .*++++=+%@@@@@@@@@@@@@@@
   :@@@@%.=.. : :--.-=:..:.::.:....-  ......... --:   ::.:.  .  :::.-  ----=#+====-==-*.           :*++=++@@@@@@@@@@@@@.
     +*#-- :.:: :-::==..::.:..:...:: .:....... . ::   :. :.      -::. ..:#=-=+-==-===-=+.+       ..  -+=++%#=-+=%@@@@#
        . ...::.--::==: ::........-:..=-   :  .   .   . .:.      :-*-    .:=-+====-==--=-+#       :.   +++++==+++++*@@*
          :.::.::-.-==-.=-:...--.: :.::-.  :            .:    :+--:.     ::.==+===---=-=+--%.      +@@=. :=*+++++++*++*
          .::::::::==---=-:.. =- .  ..: :..:  .:...  :  -. .+.   -*=:.+@@@@@@@@*====---=+*:**. .    =@@**%+:-+*%*++***+=
       . ...::::::-+=--+-=:--.+:.    ..  :.-.:::::. .:  :.*.  :-:+#@@%#++=%:-@##+===-==-=+--==+ ..   .###*+++**#@%#+*+++*=
       ..::::::::.*+--:=-----:=:-....::=:--=:....:..=. :.    ..+@@@*+==---#-=@*+*====-===+:-=*@% ::    *#*+*#+*++#%%%%##*+++-
       .::.:::::::%=--:-------: .     : -:-+#+-....= ..:     -*#::%+-:=+---:+**-+==-===-=-+-=@@@@ -#    =***#%#+*+#%==*+
      :.:::::::::-+=:---=-----. .      :. ::=..:..:   .       :   -=--:..:--+#-:-+=======-%==#@@@@:.@=   :#***%%#*+=#-==
      :-::-::::.:--*:---=-=---: . ..-+*#%#=-+:...:.                :+-....-+=::::#=======-*%-+@@@%@@-%%-  .#++*%%#*+#*+-
    . =-:::=:::::-:+.:--=-=--:- .=**+-:::+++%-..:.   .               ::..--:....:=#-=====-#@+=@@@%*%@%%@%-  -*+#%:*%++*=
      =:::---:------::-:==-=--+.      ....:  :.:.                     .   ......::*=-====-*@#-%@@%#*%%%%%%@*. +**- .*#**=
     +:::. :---=--=:=:-:==-==-:@.    .....:. ..:.                       ...::...--:*=====-+@@-*@%%*##%%*###+#*= +-  ::-:**
     ::-:   .:---.#:=.:-==-==-:%%    ....  ..:  :                              :=  ==-+==-*@@=*@%#**#%#****##*++**- .:     .
    .--      .:--:=:=-.-==-==-:%@+   ....   .:                                ::   :=--===#@@**%%**#*##***++**+=+*- ::
   :.         :----=.- -=-====-%@@:   ...   .      .                         .     :---==-@@@#%%%#*#*******+++***+# :
 .             -:--: .:-+--==-:%@@@                                              . #%:-===@@@#%##*##**+++#*+*+*+****-
                ::-:  *:%==----*+%@%   .                                        . #@%--+=*@%@%%##**#**+++%#*==+*++*+=
                -=$:-. #:+#+---:#%++%#.                      . .:. .:+          ..#@@@--**%%%%%###*+#++*++*--+*==+++-+.
                . =:: -==%@--=-=%**%%+                 =@+ .....:.:.:.         .*:@@%--%%@%%%####**#++*+++--:   .+*-==
                   :---+**%%---:@**%%#+     .      :@%%%::.:::::..:.:         .-::%%%-:@%%%%%###**#*+++=*+-::    :==:-=
               .    :=-+*##*#:-:**+*%**@:           =@#*:.::::::::::        .:...:@%%-+%%%%%###**+%*==+=%=:-.    ..    :.
               .     +*=+**%**-:=***##*+%%.        . .*%.:::::::::..       :. ....@%%=%%%#*#####+#%+===+:-:-.    .
                     .+-++**#+** +*-*++++%%%.    ..     --:.::.:::       =: .    .%%#+%%####*+@*++%+=-+. .:-
                      --++=**#*+*-++==+++%%%#@+..         .:::.        :=.  .    .%%%#*#*##*#+#=++#===:  .-
               .    . =-=+****+**+#:+==++#%%#%%%@%=. ..              :-:       .  %#%###%*##.:*+==#++-    :
                    .  :-=+=++***++#-:+++*++*#%%%%@@%=.. ..       :---.           #@@%@@@@=  :=  .+-+-
                .    . :.-===++**+==*+::+#++++*#%%%%%%%%-.     .*=:-:.            *%%%##*==+**#*+==*+=
                     :  -::====++*=+=+*==*=-=#**##%#%%%%%*+-:%#--:-. ..           .%#*=-==-*#*++==++-=#*:
                     :*::**=====+**==+=++*##*+++**##%%%%%%. :::.:. ..             .:=--===+@#*+++=+*+=-=+=*#=
                     #-=+==*=-++++#++==-++++*++++*#%%%%%%=-  .:.... .            .  -=--=+@#*#%@@%+==+=====+*+
                   ..*++==+**+:=*++%++++#++++++*+**#%%%%#-=. .:........              .@-=+++#%%@@%@=======++*@+
                .+-.-+*==*++#+-:=++*%+=**++++++*++**%%%%--=-.::..........            .: ==++*%@@%@+========+*#@@+
               -:--.=-*+*+++++=:.:-+*#+++*****=+*##%+#%==---::...........           :    .+%@@@%@#+======++*#%%@@#%=
              +::-:==--=*==**=#=:::-+#**+*+**++**%=.-++-:::--... ..  ....          :.     ..-@@@*++====++++*#%@@@%*=+.
              =---.=--:*+=+#*+=:-:--=++=**+++++*#+:=-.--:.:::..........           +        ..*%-+=-====+++*###@@@#+=+#*
              =----==-*+===@%:..-=---++##=+++***#-. .:=::...:..........         :=          :*:==-=====+++*%#%@@*++++##@*
             .+=-=*=+#*---==%:.:-=%+#+-:--+++*+*%:..  -::.............         :.          .--==-=======+*#*%@%+++==+##@#%+
             -:=##*+=-::-===+:.--+*#---::+*++++#+ ....-  .:.........  ..   . :+. .         =============+**#*++++===*%%#%###.
             :--*#@*+-::::-==-:-=#=.---:-+*==+#-......-:  ..........        :.            +============+*##**++====*%%%#**+=+
            .:---%=@*+-::--:-:.-*=:=:--=#++*@%-... . .-:.... ......       .:.           .=-===========+**+++===-===*#***+++=-:
            ..:-==+*#+*=:-::--.=+=::-=+*+%@+#@%.... ..-:.  .........     .-            .+============++========--===++**++==--
             .:----++%**-::  .+=+=++++++*%#+@@@%......-:.  .            =. .          .+-===-===-==++==--===------==+++====--:
              ..:--=*#%*+=   .=%##-:-+++*##+@@@@@.... -:.  .         ..-             -+==-======++*=======------==++======+*#*
               .::=-=#+#-  .::=#-:-:=++=+##*@@@@@@.. .::.  .         -:      .     .=+==-==+-==++=:=---=----========+**+=----:=
                .::--=+#=.:::-*=:::::++=+*#*%.#@@@@:..::.   .   .  .+           .=#*++++*+=====--=-=---=--=+**##*+=====-------:-
                 ..::-=*+::::=:.::::--===**+*. -@@@@:.::  ...  .  -.. .  .  .-%@@@*+*#*#*+====--=-:----*##*+==--==---======----:
                   ..:-:+:-:--:::--:::-+#*+++:   @@@@+:-  ..  .  +. ..   -@@@@@@@*@%*###*======*+-=-=%#=-=======-====-=======-:-+
                     ..:=::::::::::-:**++=-++.   .@@@@#= . .   :+    :#@@@@@@@@@%##%%%%#+++==#@%%@=**+==========-------=====-=+==
                       .  .:::::::--+==----+#++.  .@@@@@ .. ..:::+#%@%@@@@@@@#@%%%%%%@%*=+#@@@%@#%@=============------=====++++=+
                          ....  ..::=-:----+*=+**=++@@@@@:.-*@@%%%%%@@@@*: . .@@%%@%%@%**%@@@@@##@@*========--------=====+++*#*+==
                           .    ...::=:--==++=+++=+++%@@@@@@@%%@%@@#-      :%#%%%%@%#@@@@@@@%#@*@@+--===-----------======*##**=--
                                ...:.--:--=*+===++=++=#@@@@@%%%#*++=.     :%%%@@%%@@@@@@@@+@@#+*@@+===-----------====+++*##**+=-:
                                ....:+=:-==#++===+++===%@@%#*+==+++++++*##@@@%@@@@@@@@@**%##+=-%@#=-------------====+++*##*++=-:.
                                 ..:-+#===+#  .-:=+=*+*+#*+==+++++++++**%@@@@@@@@@@@*-@@#+=+==+@@=--------------===+++*##*+=-:.
                                  ..:=%+==+%       =#*-##*#+=%+++=++*+#%@@@@@@@@@@:%@#*=+=-+=#@@+-=-------------====+*#*++=-:.
                                     .=*===*      .--#:..-#@@-.   .:=**@@@@@@@@*@@@%+%+@@=--#@%=--:----------------=+++==-:.
                                       =::--         :*-##==-.        -@@@@@@@@@@@@@@@@@@@@@%+=::::::::::::::::::--====-:..
                                           ...        *%=-.....       %@@@@@@@@@@@@@@@@@@@@@*-::..:.............:::--:..      .-:
                                                  ::  ==.   .....    +@%@@@@@@@@@@@@@@@@@@@@*.:. . ...          .... .     =@*-:
                                                      ::..:---::... :#*#@@@@@@@@@%%@@@@@@@@@@+ .                  :*    ##+%+:
                                                             ...::::*-:::@@@@@@%##%%%%@@@@@@@#                   -+. *+ =  -:
                                                                   ..  .#@@%%%%##*+*#%@@@%%%=                    . :     ::
                                                                        @@@%%%######%%%%#####%=                =        #
                                                                          @@@@@%@@%%%###*##*-                 . .     =
                                                                          :@@%%%%###******+=-                 .
                                                                            *@###***+**+++:
                                                                               -*- =*++*:
 
 
                                         Credit for the pic: J5-daigada from deviantart
*/

#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 = 1e5 + 10;

void solve() {
    int n;
    cin >> n;
    array<vector<int>, 20> in;
    fore (i, 1, n) {
        int x;
        cin >> x;
        fore (k, 0, 19) {
            if (x & (1 << k)) {
                in[k].push_back(i);
            }
        }
    }
    int ans = 1;
    fore (k, 0, 19) {
        if (in[k].empty()) continue;
        ans = max(ans, in[k][0]);
        ans = max(ans, n - in[k].back() + 1);
        fore (i, 1, in[k].size() - 1) {
            ans = max(ans, in[k][i] - in[k][i - 1]);
        }
    }

    cout << ans << ed;
}
int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}

C. Cat, Fox and Double Maximum

原题

Fox loves permutations! She came up with the following problem and asked Cat to solve it:

You are given an even positive integer $n$ and a permutation$^\dagger$ $p$ of length $n$.

The score of another permutation $q$ of length $n$ is the number of local maximums in the array $a$ of length $n$, where $a_i = p_i + q_i$ for all $i$ ($1 \le i \le n$). In other words, the score of $q$ is the number of $i$ such that $1 < i < n$ (note the strict inequalities), $a_{i-1} < a_i$, and $a_i > a_{i+1}$ (once again, note the strict inequalities).

Find the permutation $q$ that achieves the maximum score for given $n$ and $p$. If there exist multiple such permutations, you can pick any of them.

$^\dagger$ 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

The first line of input contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases in the input you will have to solve.

The first line of each test case contains one even integer $n$ ($4 \leq n \leq 10^5$, $n$ is even) — the length of the permutation $p$.

The second line of each test case contains the $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$). It is guaranteed that $p$ is a permutation of length $n$.

It is guaranteed that the sum of $n$ across all test cases doesn’t exceed $10^5$.

Output

For each test case, output one line containing any permutation of length $n$ (the array $q$), such that $q$ maximizes the score under the given constraints.

Example

input

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

output

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

Note

In the first example, $a = [3, 6, 4, 7]$. The array has just one local maximum (on the second position), so the score of the chosen permutation $q$ is $1$. It can be proven that this score is optimal under the constraints.

In the last example, the resulting array $a = [6, 6, 12, 7, 14, 7, 14, 6]$ has $3$ local maximums — on the third, fifth and seventh positions.

翻译

狐狸喜欢排列！她提出了以下问题并请 Cat 解决：

给您一个偶数正整数 $n$ 和长度为 $n$ 的排列 $^\dagger$ $p$ 。

长度为 $n$ 的另一个排列 $q$ 的分数是长度为 $n$ 的数组 $a$ 中局部最大值的数量，其中 $a_i = p_i + q_i$ 代表所有 $i$ ( $1 \le i \le n$ )。换句话说， $q$ 的分数是 $i$ 的数量，使得 $1 < i < n$ （注意严格不等式）、 $a_{i-1} < a_i$ 和 $a_i > a_{i+1}$ （再次注意严格不等式） 。

查找给定 $n$ 和 $p$ 获得最高分数的排列 $q$ 。如果存在多个这样的排列，您可以选择其中任何一个。

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

输入
输入的第一行包含一个整数 $t$ ( $1 \leq t \leq 10^4$ ) - 输入中您必须解决的测试用例的数量。

每个测试用例的第一行包含一个 偶数 整数 $n$ （ $4 \leq n \leq 10^5$ ， $n$ 是偶数） - 排列的长度 $p$ 。

每个测试用例的第二行包含 $n$ 整数 $p_1, p_2, \ldots, p_n$ ( $1 \leq p_i \leq n$ )。保证 $p$ 是长度为 $n$ 的排列。

确保所有测试用例的 $n$ 之和不超过 $10^5$ 。

输出

对于每个测试用例，输出一行包含任意长度排列 $n$ （数组 $q$ ），使得 $q$ 在给定约束下最大化分数。

Example

input

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

output

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

笔记

在第一个示例中， $a = [3, 6, 4, 7]$ 。该数组只有一个局部最大值（在第二个位置），因此所选排列 $q$ 的得分为 $1$ 。可以证明这个分数在约束条件下是最优的。

在最后一个示例中，生成的数组 $a = [6, 6, 12, 7, 14, 7, 14, 6]$ 具有 $3$ 局部最大值 - 位于第三、第五和第七位置。

思路

​ …..

代码

1
// 持续....