Codeforces Round #627 (Div. 3) 题解（A-E）

A. Yet Another Tetris Problem

You are given some Tetris field consisting of nn columns. The initial height of the ii-th column of the field is aiai blocks. On top of these columns you can place only figures of size 2×12×1 (i.e. the height of this figure is 22 blocks and the width of this figure is 11 block). Note that you cannot rotate these figures.

Your task is to say if you can clear the whole field by placing such figures.

More formally, the problem can be described like this:

The following process occurs while at least one aiai is greater than 00:

1. You place one figure 2×12×1 (choose some ii from 11 to nn and replace aiai with ai+2ai+2);
2. then, while all aiai are greater than zero, replace each aiai with ai−1ai−1.

And your task is to determine if it is possible to clear the whole field (i.e. finish the described process), choosing the places for new figures properly.

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤1001≤t≤100) — the number of test cases.

The next 2t2t lines describe test cases. The first line of the test case contains one integer nn (1≤n≤1001≤n≤100) — the number of columns in the Tetris field. The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1001≤ai≤100), where aiai is the initial height of the ii-th column of the Tetris field.

Output

For each test case, print the answer — "YES" (without quotes) if you can clear the whole Tetris field and "NO" otherwise.

Example

input

4
3
1 1 3
4
1 1 2 1
2
11 11
1
100

output

YES
NO
YES
YES

Note

The first test case of the example field is shown below:

Gray lines are bounds of the Tetris field. Note that the field has no upper bound.

One of the correct answers is to first place the figure in the first column. Then after the second step of the process, the field becomes [2,0,2][2,0,2]. Then place the figure in the second column and after the second step of the process, the field becomes [0,0,0][0,0,0].

And the second test case of the example field is shown below:

It can be shown that you cannot do anything to end the process.

In the third test case of the example, you first place the figure in the second column after the second step of the process, the field becomes [0,2][0,2]. Then place the figure in the first column and after the second step of the process, the field becomes [0,0][0,0].

In the fourth test case of the example, place the figure in the first column, then the field becomes [102][102] after the first step of the process, and then the field becomes [0][0] after the second step of the process.

题意：就是看看每个数字对2取余得到的值是否相同。

代码：

#include <cstdio>
#include <cstdio>
using namespace std;
const int M = 105;
int a[M], n, T;

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i=1;i<=n;i++)
            scanf("%d", &a[i]);
        int f = a[1] % 2;
        bool flag = false;
        for (int i=2;i<=n;i++)
        {
            if (a[i] % 2 != f)
            {
                flag = true;
                break;
            }
        }
        if (flag) puts("NO");
        else puts("YES");
    }
    return 0;
}

 

B. Yet Another Palindrome Problem

 

You are given an array aa consisting of nn integers.

Your task is to determine if aa has some subsequence of length at least 33 that is a palindrome.

Recall that an array bb is called a subsequence of the array aa if bb can be obtained by removing some (possibly, zero) elements from aa (not necessarily consecutive) without changing the order of remaining elements. For example, [2][2], [1,2,1,3][1,2,1,3] and [2,3][2,3] are subsequences of [1,2,1,3][1,2,1,3], but [1,1,2][1,1,2] and [4][4] are not.

Also, recall that a palindrome is an array that reads the same backward as forward. In other words, the array aa of length nn is the palindrome if ai=an−i−1ai=an−i−1 for all ii from 11 to nn. For example, arrays [1234][1234], [1,2,1][1,2,1], [1,3,2,2,3,1][1,3,2,2,3,1] and [10,100,10][10,100,10] are palindromes, but arrays [1,2][1,2] and [1,2,3,1][1,2,3,1] are not.

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤1001≤t≤100) — the number of test cases.

Next 2t2t lines describe test cases. The first line of the test case contains one integer nn (3≤n≤50003≤n≤5000) — the length of aa. The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n), where aiai is the ii-th element of aa.

It is guaranteed that the sum of nn over all test cases does not exceed 50005000 (∑n≤5000∑n≤5000).

Output

For each test case, print the answer — "YES" (without quotes) if aa has some subsequence of length at least 33 that is a palindrome and "NO" otherwise.

Example

input

Copy

5
3
1 2 1
5
1 2 2 3 2
3
1 1 2
4
1 2 2 1
10
1 1 2 2 3 3 4 4 5 5

output

Copy

YES
YES
NO
YES
NO

Note

In the first test case of the example, the array aa has a subsequence [1,2,1][1,2,1] which is a palindrome.

In the second test case of the example, the array aa has two subsequences of length 33 which are palindromes: [2,3,2][2,3,2] and [2,2,2][2,2,2].

In the third test case of the example, the array aa has no subsequences of length at least 33 which are palindromes.

In the fourth test case of the example, the array aa has one subsequence of length 44 which is a palindrome: [1,2,2,1][1,2,2,1] (and has two subsequences of length 33 which are palindromes: both are [1,2,1][1,2,1]).

In the fifth test case of the example, the array aa has no subsequences of length at least 33 which are palindromes.

 

题意：检查每个序列的回文子序列长度是否大于等于三。

思路：将给出的序列逆序得到一个新序列。两个序列的最大公共子序列即最长的回文子序列。O(n^2)的LCS解决。

#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int M = 5010;
int a[M], T, n, dp[M][M];

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        memset(dp, 0, sizeof(dp));
        scanf("%d", &n);
        for (int i=1;i<=n;i++)
            scanf("%d", &a[i]);
        for (int i=1;i<=n;i++)
        {
            for (int j=n;j>=1;j--)  //n-j+1
            {
                if (a[i] == a[j])
                    dp[i][n-j+1] = dp[i-1][n-j] + 1;
                else
                    dp[i][n-j+1] = max(dp[i][n-j], dp[i-1][n-j+1]);
            }
        }
        if (dp[n][n] >= 3) printf("YES
");
        else printf("NO
");
    }
    return 0;
}

C. Frog Jumps

There is a frog staying to the left of the string s=s1s2…sns=s1s2…sn consisting of nn characters (to be more precise, the frog initially stays at the cell 00). Each character of ss is either 'L' or 'R'. It means that if the frog is staying at the ii-th cell and the ii-th character is 'L', the frog can jump only to the left. If the frog is staying at the ii-th cell and the ii-th character is 'R', the frog can jump only to the right. The frog can jump only to the right from the cell 00.

Note that the frog can jump into the same cell twice and can perform as many jumps as it needs.

The frog wants to reach the n+1n+1-th cell. The frog chooses some positive integer value dd before the first jump (and cannot change it later) and jumps by no more than dd cells at once. I.e. if the ii-th character is 'L' then the frog can jump to any cell in a range [max(0,i−d);i−1][max(0,i−d);i−1], and if the ii-th character is 'R' then the frog can jump to any cell in a range [i+1;min(n+1;i+d)][i+1;min(n+1;i+d)].

The frog doesn't want to jump far, so your task is to find the minimum possible value of dd such that the frog can reach the cell n+1n+1 from the cell 00 if it can jump by no more than dd cells at once. It is guaranteed that it is always possible to reach n+1n+1 from 00.

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases.

The next tt lines describe test cases. The ii-th test case is described as a string ss consisting of at least 11 and at most 2⋅1052⋅105 characters 'L' and 'R'.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed 2⋅1052⋅105 (∑|s|≤2⋅105∑|s|≤2⋅105).

Output

For each test case, print the answer — the minimum possible value of dd such that the frog can reach the cell n+1n+1 from the cell 00 if it jumps by no more than dd at once.

Example

input

Copy

6
LRLRRLL
L
LLR
RRRR
LLLLLL
R

output

Copy

3
2
3
1
7
1

Note

The picture describing the first test case of the example and one of the possible answers:

In the second test case of the example, the frog can only jump directly from 00 to n+1n+1.

In the third test case of the example, the frog can choose d=3d=3, jump to the cell 33 from the cell 00 and then to the cell 44 from the cell 33.

In the fourth test case of the example, the frog can choose d=1d=1 and jump 55 times to the right.

In the fifth test case of the example, the frog can only jump directly from 00 to n+1n+1.

In the sixth test case of the example, the frog can choose d=1d=1 and jump 22 times to the right.

题意：给出一串由L， R组成的字符串。青蛙每次跳最多d步，要求跳到L要往左跳，跳到R要往右跳。求最小的d。

思路：每次要跳跃的最优解，肯定是跳到连续的R中的最后一个R，再向右跳。那么跳到L是没有用的。因为是从R跳到L的，L往回跳完全没有必要。直接跨过L就行了。所以答案就是L的最长连续数量+1。

#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 2e5+5;
char str[M];
int n, T, l;

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s", str);
        l = strlen(str);
        int cnt = 0, ans = 0;
        for (int i=0;i<l;i++)
        {
            if (str[i] == 'L')
            {
                cnt++;
            } if(str[i] == 'R')
            {
                ans = max(cnt, ans);
                cnt = 0;
            }
        }
        ans = max(cnt, ans);
        printf("%d
", ans+1);
    }
    return 0;
}

D. Pair of Topics

The next lecture in a high school requires two topics to be discussed. The ii-th topic is interesting by aiai units for the teacher and by bibi units for the students.

The pair of topics ii and jj (i<ji<j) is called good if ai+aj>bi+bjai+aj>bi+bj (i.e. it is more interesting for the teacher).

Your task is to find the number of good pairs of topics.

Input

The first line of the input contains one integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the number of topics.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109), where aiai is the interestingness of the ii-th topic for the teacher.

The third line of the input contains nn integers b1,b2,…,bnb1,b2,…,bn (1≤bi≤1091≤bi≤109), where bibi is the interestingness of the ii-th topic for the students.

Output

Print one integer — the number of good pairs of topic.

Examples

input

Copy

5
4 8 2 6 2
4 5 4 1 3

output

Copy

7

input

Copy

4
1 3 2 4
1 3 2 4

output

Copy

0


题意：n个主题，ai表示老师对其的喜爱度，bi表示学生对其的喜爱度，要选出一对主题i和j，使得ai + aj > bi + bj（王侯将相宁有种乎？）。求出满足要求的主题对数。
思路：用ci表示ai-bi，则方程等价于-ci < cj。那么我们对于每一个i，只要在有序的c序列中二分查找找到大于-ci的cj即可，答案即每一次的n-j+1之和。
代码：

#include <bits/stdc++.h>
using namespace std;
const int M = 2e5+10;
typedef long long ll;
ll a[M], b[M], c[M], n;

int main()
{
    scanf("%d", &n);
    for (int i=1;i<=n;i++)
        scanf("%d", &a[i]);
    for (int i=1;i<=n;i++)
        scanf("%d", &b[i]);
    for (int i=1;i<=n;i++)
        c[i] = a[i] - b[i];
    sort(c+1, c+1+n);
    ll ans = 0;
    for (int i=1;i<=n;i++)
    {
        ll cnt = upper_bound(c+i+1, c+n+1, -c[i]) - c;
        ans += n - cnt + 1;
    }
    printf("%lld
", ans);
    return 0;
}

E. Sleeping Schedule

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Vova had a pretty weird sleeping schedule. There are hh hours in a day. Vova will sleep exactly nn times. The ii-th time he will sleep exactly after aiai hours from the time he woke up. You can assume that Vova woke up exactly at the beginning of this story (the initial time is 00). Each time Vova sleeps exactly one day (in other words, hh hours).

Vova thinks that the ii-th sleeping time is good if he starts to sleep between hours ll and rr inclusive.

Vova can control himself and before the ii-th time can choose between two options: go to sleep after aiai hours or after ai−1ai−1 hours.

Your task is to say the maximum number of good sleeping times Vova can obtain if he acts optimally.

Input

The first line of the input contains four integers n,h,ln,h,l and rr (1≤n≤2000,3≤h≤2000,0≤l≤r<h1≤n≤2000,3≤h≤2000,0≤l≤r<h) — the number of times Vova goes to sleep, the number of hours in a day and the segment of the good sleeping time.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai<h1≤ai<h), where aiai is the number of hours after which Vova goes to sleep the ii-th time.

Output

Print one integer — the maximum number of good sleeping times Vova can obtain if he acts optimally.

Example

input

Copy

7 24 21 23
16 17 14 20 20 11 22

output

Copy

3

Note

The maximum number of good times in the example is 33.

The story starts from t=0t=0. Then Vova goes to sleep after a1−1a1−1 hours, now the time is 1515. This time is not good. Then Vova goes to sleep after a2−1a2−1 hours, now the time is 15+16=715+16=7. This time is also not good. Then Vova goes to sleep after a3a3 hours, now the time is 7+14=217+14=21. This time is good. Then Vova goes to sleep after a4−1a4−1 hours, now the time is 21+19=1621+19=16. This time is not good. Then Vova goes to sleep after a5a5 hours, now the time is 16+20=1216+20=12. This time is not good. Then Vova goes to sleep after a6a6 hours, now the time is 12+11=2312+11=23. This time is good. Then Vova goes to sleep after a7a7 hours, now the time is 23+22=2123+22=21. This time is also good.

 

题意：给出n个数，t=0，每次t可以加上ai或者ai - 1，大于h后减去h。若每次执行操作后l <= t <= r，则cnt++。求出cnt的最大值。

思路：动态规划

　　状态：dp[i][j]表示第i次时间为j的cnt最大值。

　　状态转移方程：dp[i][j] = max(dp[i][j], dp[i - 1][( j + h - a[i] ) % h] + (j <= r && j >= l), dp[i - 1][( j + h - a[i] + 1 ) % h] + (j <= r && j >= l) )。

　　细节：每次转移是从这次睡了ai小时和ai-1小时的状态转移过来的，所以将dp数组初始化为-INF，再初始化dp[0][0]为0，可以保证从dp[0][0]转移到每一个可能的状态，其他转移不到的状态即使遍历到了不会填上值。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2020;
int n, h, l, r, a[N], ans, dp[N][N];
int main()
{
    scanf("%d%d%d%d", &n, &h, &l, &r);
    for (int i=1;i<=n;i++)
        scanf("%d", &a[i]);
    memset(dp, -0x3f, sizeof(dp));
    dp[0][0] = 0;
    int mx = 0;
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<=h;j++)
        {
            dp[i][j] = max(dp[i-1][(j-a[i]+h) % h] + (j <= r && j >= l), dp[i][j]);
            dp[i][j] = max(dp[i-1][(j-a[i]+1+h) % h] + (j <= r && j >= l), dp[i][j]);
            mx = max(mx, dp[i][j]);
        }
    }
    printf("%d
", mx);
    return 0;
}

 F. Maximum White Subtree

对于F题，不是我吹，我连题目都没看懂。