A. Yet Another Tetris Problem

You are given some Tetris field consisting of n columns. The initial height of the i-th column of the field is ai 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 aia_i is greater than 00:
You place one figure 2×12×1 (choose some ii from 11 to nn and replace aia_i with ai+2a_i+2);
then, while all ai are greater than zero, replace each aia_i with ai−1a_i−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 t independent test cases.

Input

The first line of the input contains one integer t(1≤t≤100)t (1≤t≤100) — the number of test cases.
The next 2t2t lines describe test cases. The first line of the test case contains one integer n(1≤n≤100)n (1≤n≤100) — the number of columns in the Tetris field. The second line of the test case contains n integers a1,a2,…,an(1≤ai≤100)a_1,a_2,…,a_n (1≤a_i≤100), where aia_i 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.

Translation

玩俄罗斯方块，但是只能一次竖着放几个2×12\times 1的方块。问能不能一次性把所有方块消除。

Idea

消除方块就要填满所有的坑，如果相邻两个方块直接相差的个数是22的倍数，那就能用几个2×12\times 1的方块竖着填满。

Code

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
#include<iostream>
#include<cstdio>
using namespace std;
void solve()
{
	int n;
	cin>>n;
	int a[103];
	int i;
	bool ok=1;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(i=1;i<n;i++)
	{
		if((a[i+1]-a[i])&1)
		{
			ok=0;
			break;
		}
	}
	if(ok) puts("YES");
	else puts("NO");
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

Postscript

一开始wawa了一发，把条件语句写成了if((a[i+1]-a[i])%2==1)，如果a[i+1]−a[i]<0a[i+1]-a[i]<0就尴尬了。

B. Yet Another Palindrome Problem

You are given an array a consisting of n integers.
Your task is to determine if a has some subsequence of length at least 33 that is a palindrome.
Recall that an array b is called a subsequence of the array a if b can be obtained by removing some (possibly, zero) elements from a (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−1a_i=a_n−i−1 for all ii from 11 to n. For example, arrays [1234],[1,2,1],[1,3,2,2,3,1][1234], [1,2,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 t independent test cases.

Input

The first line of the input contains one integer t(1≤t≤100)t (1≤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≤5000)(3≤n≤5000) — the length of aa. The second line of the test case contains nn integers a1,a2,…,an(1≤ai≤n)a_1,a_2,…,a_n (1≤a_i≤n), where aia_i is the ii-th element of aa.
It is guaranteed that the sum of n over all test cases does not exceed 50005000$ (∑n≤5000)$.

Output

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

Example

input
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
YES
YES
NO
YES
NO
Note
In the first test case of the example, the array a has a subsequence [1,2,1][1,2,1] which is a palindrome.
In the second test case of the example, the array a 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 a has no subsequences of length at least 33 which are palindromes.
In the fourth test case of the example, the array a 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 a has no subsequences of length at least 33 which are palindromes.

Translation

问是否能在数列aa中找到一个长度大于等于33的回文子序列。

Idea

只需要满足最低要求，找数列中长度为33的回文子序列即可。
这样的子序列存在满足两个条件

  • 有两个重复数字
  • 两个重复数字之间的索引差值大于11

Code

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
#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
using namespace std;
const int N=5003;
void solve()
{
	vector<int>pos[N];//记录每一个数字的位置
	map<int,int>cnt;//记录每个数字的个数
	vector<int>has;//记录出现次数大于等于2的数字
	int n;
	cin>>n;
	int i;
	for(i=1;i<=n;i++)
	{
		int temp;
		cin>>temp;
		cnt[temp]++;
		pos[temp].push_back(i);
	}
	bool ok=0;
	map<int,int>::iterator it;
	for(it=cnt.begin();it!=cnt.end();it++)
	{
		if(it->second>=2) 
		{
			has.push_back(it->first);
		}
	}
	for(auto v:has)//遍历满足条件1的数字
	{
		if(pos[v].size()==2)
		{
			if(abs(pos[v][0]-pos[v][1])==1) 
			{
				continue;
			}
			else //索引差值要大于1
			{
				ok=1;
				break;
			}
		}
		else if(pos[v].size()>2)//有3个或3个以上，必有回文子序列。
		{
			ok=1;
			break;
		}
	}
	if(ok) puts("YES");
	else puts("NO");
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}

C. Frog Jumps

There is a frog staying to the left of the string s=s1s2…sns = s_1 s_2 \ldots s_n 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+1)(n+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 t independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤104)(1≤t≤10^4) — the number of test cases.
The next t lines describe test cases. The ii-th test case is described as a string s consisting of at least 11 and at most 2⋅1052⋅10^5 characters ‘L’ and ‘R’.
It is guaranteed that the sum of lengths of strings over all test cases does not exceed 2⋅1052⋅10^5 (∑∣s∣≤2⋅105)(∑|s|≤2⋅10^5).

Output

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

Example

input

6
LRLRRLL
L
LLR
RRRR
LLLLLL
R

output

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 0 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.

Translation

青蛙在一排只有’L’和’R’的字符串（字符串从1~n）上跳，碰到’L’向左跳，碰到’R’向右跳，青蛙每次最多能跳dd个长度，问使得青蛙能从00跳到n+1n+1的最小的dd。

Idea

根据，我们根本不需要向左跳。 这只会远离我们的目标，因为在向左跳后我们的自由度降低了。 为了最小化dd，我们只需要在最接近的’R’单元之间跳转即可。任务就是求出相邻’R’的最大间隔。
因为要从00跳转到n+1n+1，所以开头和末尾添加一个为’R’的格子。

Code

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
#include<iostream>
#include<string>
using namespace std;
void solve()
{
	string s;
	cin>>s;
	s='R'+s+'R';
	int i;
	int last=0;
	int d=-0x3f3f3f3f; 
	int len=s.length()-1;//截掉最前端
	for(i=1;i<=len;i++)
	{
		if(s[i]=='R')
		{
			d=max(d,i-last);
			last=i;
		}
	}
	cout<<d<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
	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 ai units for the teacher and by bi units for the students.
The pair of topics ii and jj (i<j)(i<j) is called good if ai+aj>bi+bja_i+a_j>b_i+b_j (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 n(2≤n≤2⋅105)n (2≤n≤2⋅10^5) — the number of topics.
The second line of the input contains nn integers a1,a2,…,an(1≤ai≤109)a_1,a_2,…,a_n (1≤a_i≤10^9), where aia_i is the interestingness of the ii-th topic for the teacher.
The third line of the input contains nn integers b1,b2,…,bn(1≤bi≤109)b_1,b_2,…,b_n (1≤b_i≤10^9), where bib_i is the interestingness of the ii-th topic for the students.

Output

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

Examples

input

5
4 8 2 6 2
4 5 4 1 3

output

7

input

4
1 3 2 4
1 3 2 4

output

0

Translation

给两个数列${ a_n } , { b_n } ，求满足，求满足a_i+a_j>b_i+b_j(i<j)的的(i,j)$对的个数。

Idea

ai+aj>bi+bj⇔ai−bi>aj−bja_i+a_j>b_i+b_j\Leftrightarrow a_i-b_i>a_j-b_j，令c=a−bc=a-b，则问题转化为求ci+cj>0(i<j)c_i+c_j>0(i<j)的(i,j)(i,j)对的个数，实际上就是在数列{cn}\{ c_n \}中不考虑顺序地不重复得选取xx个满足条件的数对，问xx的最大值。
将{cn}\{ c_n \}从大到小排序，可以用对于每一个cic_i，若ci<=0c_i<=0，在cic_i前面一定找不到使得ci+cj>0c_i+c_j>0的jj；若ci>0c_i>0，需要二分找到第一个大于−ci-c_i的数字的位置pospos，那么答案增加i−posi-pos。

Code

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
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll c[200005];
int n;
ll ans=0;
void solve()
{
	int i;
	cin>>n;
	for(i=1;i<=n;i++) cin>>c[i];
	for(i=1;i<=n;i++)
	{
		ll temp;
		cin>>temp;
		c[i]-=temp;
	}
	sort(c+1,c+1+n);
	for(i=1;i<=n;i++)
	{
		if(c[i]<=0) continue;
		else
		{
			int pos;
			//STL使用
			pos=upper_bound(c+1,c+1+n,-c[i])-c;
			ans+=i-pos;
		}
	}
	cout<<ans;
}
int main()
{
	solve();
	return 0;
}

E. Sleeping Schedule

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 aia_i 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 aia_i hours or after ai−1a_i−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<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 n integers a1,a2,…,an(1≤ai<h)a_1, a_2, \dots, a_n(1 \le a_i < h), where aia_i 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

7 24 21 23
16 17 14 20 20 11 22

output

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−1a_1−1 hours, now the time is 1515. This time is not good. Then Vova goes to sleep after a2−1a_2−1 hours, now the time is 15+16=715+16=7. This time is also not good. Then Vova goes to sleep after a3a_3 hours, now the time is 7+14=217+14=21. This time is good. Then Vova goes to sleep after a4−1a_4−1 hours, now the time is 21+19=1621+19=16. This time is not good. Then Vova goes to sleep after a5a_5 hours, now the time is 16+20=1216+20=12. This time is not good. Then Vova goes to sleep after a6a_6 hours, now the time is 12+11=2312+11=23. This time is good. Then Vova goes to sleep after a7a_7 hours, now the time is 23+22=2123+22=21. This time is also good.

Translation

一天有hh小时，主人公要睡nn次觉，第ii次睡觉可以睡aia_i小时或者ai−1a_i-1个小时，醒了马上就要睡下一觉，直到睡完nn次，如果睡觉起来的时刻在ll到rr之间，那么这一觉就是goodgood，加一分，问睡完这nn次，最多得多少分。

Idea

此题是一个最优化问题，且满足最优子结构，考虑使用DPDP。
正如官方题解所说：“This is a very standard dynamic programming problem.”然而我wa了5次，比赛结束了还没做出来。
dp[i][j]dp[i][j]表示睡完第ii次时，有jj次睡了ak−1(k∈[1,i])a_k-1(k\in [1,i])个小时，i−ji-j次睡了ak(k∈[1,i])a_k(k\in [1,i])个小时的最大得分。
转移方程很好想，dp[i][j]dp[i][j]由dp[i−1][j]dp[i-1][j]和dp[i−1][j−1]dp[i-1][j-1]得到。转移后需要判断dp[i][j]dp[i][j]的状态是否good。

Code

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
#include<iostream>
using namespace std;
const int N=2005;
int dp[N][N];
int n,h,l,r;
int t[N];
void read()
{
	cin>>n>>h>>l>>r;
	int i;
	for(i=1;i<=n;i++) cin>>t[i];
}
void solve()
{
	read();
	int i,j;
	int sum=0;
	for(i=1;i<=n;i++)
	{
		sum+=t[i];//累计时间
		for(j=0;j<=i;j++)
		{
			if(j==0) dp[i][j]=dp[i-1][j];//每次都睡满
			else if(j==i) dp[i][j]=dp[i-1][j-1];//每次都少睡一小时
			else dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]);//只能在两种情况中选一个
			int now=(sum-j)%h;//减去多算的j小时再取模
			dp[i][j]+=(l<=now&&now<=r);//判断good
		} 
	}
	int ans=0;
	//找n次睡觉的最大值
	for(j=0;j<=n;j++) ans=max(ans,dp[n][j]);
	cout<<ans;
}
int main()
{
	solve();
	return 0;
}

Postscript

DPDP完成后，找答案的循环必须从dp[n][0]dp[n][0]开始。