Codeforces summer training weekly (7.21~7.27)

A. Flipping Game

time limit per test: 1 second

memory limit per test:  256 megabytes

input: standard input

output: standard output

Iahub got bored, so he invented a game to be played on paper.

He writes n integers a1, a2, ..., an. Each of those integers can be either 0 or 1. He's allowed to do exactly one move: he chooses two indices i and j (1 ≤ i ≤ j ≤ n) and flips all values ak for which their positions are in range [i, j] (that is i ≤ k ≤ j). Flip the value of x means to apply operation x = 1 - x.

The goal of the game is that after exactly one move to obtain the maximum number of ones. Write a program to solve the little game of Iahub.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 100). In the second line of the input there are n integers: a1, a2, ..., an. It is guaranteed that each of those n values is either 0 or 1.

Output

Print an integer — the maximal number of 1s that can be obtained after exactly one move.

Examples

input

5
1 0 0 1 0

output

4

input

4
1 0 0 1

output

4

Note

In the first case, flip the segment from 2 to 5 (i = 2, j = 5). That flip changes the sequence, it becomes: [1 1 1 0 1]. So, it contains four ones. There is no way to make the whole sequence equal to [1 1 1 1 1].

In the second case, flipping only the second and the third element (i = 2, j = 3) will turn all numbers into 1.

Answer key ：

        This way 1200 The sub topics are still of high quality , First, consider the special situation , I.e. complete 0 Or all 1, Because this question must be turned over once , therefore If it's all 1 The answer is n-1, whole 0 The answer is n. General situation , namely 0、1 When mixed , We have to flip as much as possible 0, So I used double circulation to solve , That is, for each item , Judge whether it turns over from the current point to the next point 1 Maximum number of , namely c0-c1 The maximum of , Finally, add the original 1 The number of is the final answer .

AC Code ：

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N=100+5;
int a[N];
void solve(){
	int n,cur=0;
	cin>>n;
	for (int i=0;i<n;i++){
		cin>>a[i];
		if (a[i]==1){
			cur++;
		}
	}
	if (cur==n){
		cout<<n-1<<endl;
		return;
	}
	else if (cur==0){
		cout<<n<<endl;
		return;
	}
	int ans=0;
	for (int i=0;i<n;i++){
		int c0=0,c1=0;
		for (int j=i;j<n;j++){
			if (a[j]==0){
				c0++;
			}
			else if (a[j]==1){
				c1++;
			}
			if (c0-c1>ans){
				ans=c0-c1;
			}
		}
	}
	cout<<ans+cur<<endl;
}
int main()
{
	int _;
	//cin>>_;
	_=1; 
	while (_--){
		solve();
	}
	return 0;
}

---

B. Worms

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

It is lunch time for Mole. His friend, Marmot, prepared him a nice game for lunch.

Marmot brought Mole n ordered piles of worms such that i-th pile contains ai worms. He labeled all these worms with consecutive integers: worms in first pile are labeled with numbers 1 to , worms in second pile are labeled with numbers  to  and so on. See the example for a better understanding.

Mole can't eat all the worms (Marmot brought a lot) and, as we all know, Mole is blind, so Marmot tells him the labels of the best juicy worms. Marmot will only give Mole a worm if Mole says correctly in which pile this worm is contained.

Poor Mole asks for your help. For all juicy worms said by Marmot, tell Mole the correct answers.

Input

The first line contains a single integer n (1 ≤ n ≤ ), the number of piles.

The second line contains n integers  (1 ≤ ≤ , ), where  is the number of worms in the i-th pile.

The third line contains single integer m (1 ≤ m ≤ ), the number of juicy worms said by Marmot.

The fourth line contains m integers  (1 ≤ ≤ ), the labels of the juicy worms.

Output

Print m lines to the standard output. The i-th line should contain an integer, representing the number of the pile where the worm labeled with the number  is. 

Examples

input

5
2 7 3 4 9
3
1 25 11

output

1
5
3

Note

For the sample input:

• The worms with labels from [1, 2] are in the first pile.
• The worms with labels from [3, 9] are in the second pile.
• The worms with labels from [10, 12] are in the third pile.
• The worms with labels from [13, 16] are in the fourth pile.
• The worms with labels from [17, 25] are in the fifth pile.

Answer key ：

        Compared with the previous topic , This problem is very simple , The title can be done as you say , Set the specified interval to the corresponding number , Finally, output directly according to the numerical value , Notice the range of the array .

AC Code ：

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N=1e6+5;
int a[N],b[N];
void solve(){
	int n;
	cin>>n;
	int cur=0,sum=0;
	for (int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
		for (int j=cur;j<=sum;j++){
			b[j]=i;
		}
		cur=sum+1;
	}
	int q;
	cin>>q;
	while (q--){
		int x;
		cin>>x;
		cout<<b[x]<<endl;
	}
}
int main()
{
	int _;
	//cin>>_;
	_=1; 
	while (_--){
		solve();
	}
	return 0;
}

---

B. Books

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

When Valera has got some free time, he goes to the library to read some books. Today he's got t free minutes to read. That's why Valera took n books in the library and for each book he estimated the time he is going to need to read it. Let's number the books by integers from 1 to n. Valera needs  minutes to read the i-th book.

Valera decided to choose an arbitrary book with number i and read the books one by one, starting from this book. In other words, he will first read book number i, then book number i + 1, then book number i + 2 and so on. He continues the process until he either runs out of the free time or finishes reading the n-th book. Valera reads each book up to the end, that is, he doesn't start reading the book if he doesn't have enough free time to finish reading it.

Print the maximum number of books Valera can read.

Input

The first line contains two integers n and t (1 ≤ n ≤ ; 1 ≤ t ≤ ) — the number of books and the number of free minutes Valera's got. The second line contains a sequence of n integers  (1 ≤ ai ≤ ), where number shows the number of minutes that the boy needs to read the i-th book. 

Output

Print a single integer — the maximum number of books Valera can read.

Examples

input

4 5
3 1 2 1

output

3

input

3 3
2 2 3

output

1

Answer key ：

        Another 1400 The title of the sub section , This time, it needs to be slightly changed on the dichotomy template . The title means from i Items are read sequentially （ At the beginning, I accidentally understood the meaning of the wrong question ）, Finally, take the maximum value of the number that can be read , So we have to traverse every item , namely From i Item start to n term , Make a binary search , Take out the biggest one , namely max(ans,l-i).

AC Code ： 

#include <bits/stdc++.h>
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ll long long
using namespace std;

const int N=1e5+5;
int a[N];
ll sum[N];
void solve(){
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	int ans=0;
	for (int i=1;i<=n;i++){
		if (a[i]>m){
			continue;
		}
		int l=i,r=n;
		while (l<=r){
			int mid=(l+r)>>1;
			if (sum[mid]-sum[i-1]>m){
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
		ans=max(ans,l-i);
	}
	cout<<ans<<endl;
}
int main()
{
	BUFF;
	int _;
	//cin>>_;
	_=1; 
	while (_--){
		solve();
	}
	return 0;
}

---

B. Pashmak and Flowers

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

Pashmak decided to give Parmida a pair of flowers from the garden. There are n flowers in the garden and the i-th of them has a beauty number . Parmida is a very strange girl so she doesn't want to have the two most beautiful flowers necessarily. She wants to have those pairs of flowers that their beauty difference is maximal possible!

Your task is to write a program which calculates two things:

1. The maximum beauty difference of flowers that Pashmak can give to Parmida.
2. The number of ways that Pashmak can pick the flowers. Two ways are considered different if and only if there is at least one flower that is chosen in the first way and not chosen in the second way.

Input

The first line of the input contains n (2 ≤ n ≤ 2·). In the next line there are n space-separated integers  (1 ≤ bi ≤ ).

Output

The only line of output should contain two integers. The maximum beauty difference and the number of ways this may happen, respectively.

Examples

input

2
1 2

output

1 1

input

3
1 4 5

output

4 1

input

5
3 1 2 3 1

output

2 4

Note

In the third sample the maximum beauty difference is 2 and there are 4 ways to do this:

1. choosing the first and the second flowers;
2. choosing the first and the fifth flowers;
3. choosing the fourth and the second flowers;
4. choosing the fourth and the fifth flowers.

  Answer key ：

        open long long！ open long long！ open long long！ Important things are to be repeated for 3 times ！

        The topic is very simple , Pay attention to the discussion according to the situation , If the first and last elements are the same after sorting , So the result is n*(n-1)/2, Otherwise, the number of the first and last elements is multiplied , Must open long long,int Explosive ！

AC Code ：

#include <bits/stdc++.h>
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ll long long
using namespace std;

const int N=2e5+5;
ll a[N];
map<ll,ll> mp;
void solve(){
	ll n;
	cin>>n;
	for (int i=0;i<n;i++){
		cin>>a[i];
		mp[a[i]]++;
	}
	sort(a,a+n);
	if (a[0]==a[n-1]){
		cout<<a[n-1]-a[0]<<" "<<n*(n-1)/2<<endl;
		return;
	}
	cout<<a[n-1]-a[0]<<" "<<mp[a[0]]*mp[a[n-1]]<<endl;
}
int main()
{
	BUFF;
	int _;
	//cin>>_;
	_=1; 
	while (_--){
		solve();
	}
	return 0;
}

---

C. Alternating Subsequence

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

Recall that the sequence b is a a subsequence of the sequence a if b can be derived from a by removing zero or more elements without changing the order of the remaining elements. For example, if a=[1,2,1,3,1,2,1], then possible subsequences are: [1,1,1,1], [3] and [1,2,1,3,1,2,1], but not [3,2,3] and [1,1,1,1,2].

You are given a sequence a consisting of n positive and negative elements (there is no zeros in the sequence).

Your task is to choose maximum by size (length) alternating subsequence of the given sequence (i.e. the sign of each next element is the opposite from the sign of the current element, like positive-negative-positive and so on or negative-positive-negative and so on). Among all such subsequences, you have to choose one which has the maximum sum of elements.

In other words, if the maximum length of alternating subsequence is k then your task is to find the maximum sum of elements of some alternating subsequence of length k.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ ) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1 ≤ n ≤ 2⋅) — the number of elements in a. The second line of the test case contains n integers  (), where  is the i-th element of a.

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

Output

For each test case, print the answer — the maximum sum of the maximum by size (length) alternating subsequence of a.

Example

input

4
5
1 2 3 -1 -2
4
-1 -2 -1 -3
10
-2 8 3 8 -4 -15 5 -2 -3 1
6
1 -1000000000 1 -1000000000 1 -1000000000

output

2
-1
6
-2999999997

Note

In the first test case of the example, one of the possible answers is [1,2,3,−1,−2].

In the second test case of the example, one of the possible answers is [−1,−2,-1,−3].

In the third test case of the example, one of the possible answers is [−2,8,3,8,−4,−15,5,−2,−3,1].

In the fourth test case of the example, one of the possible answers is [1,−1000000000,1,−1000000000,1,−1000000000].

Answer key ：

        There are many solutions to this problem , Here I use the strategy of stack simulation . Because the title requires finding the longest sequence , So start with the first number , Push the first number onto the stack , And then go back through , If the stack top element and a[i] The symbols are different , Just put a[i] Push to stack , Otherwise, take the maximum of the two , Guaranteed the final sum The largest can also ensure that this sequence is the longest .

AC Code ：

#include <bits/stdc++.h>
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ll long long
using namespace std;

const int N=2e5+5;
ll a[N];
void solve(){
	int n;
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	stack<ll> st;
	st.push(a[1]);
	for (int i=2;i<=n;i++){
		if (st.top()*a[i]<0){
			st.push(a[i]);
		}
		else{
			st.top()=max(st.top(),a[i]);
		}
	}
	ll sum=0;
	while (!st.empty()){
		sum+=st.top();
		st.pop();
	}
	cout<<sum<<endl;
}
int main()
{
	BUFF;
	int _;
	cin>>_;
	//_=1; 
	while (_--){
		solve();
	}
	return 0;
}

---

B. Random Teams

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

n participants of the competition were split into m teams in some manner so that each team has at least one participant. After the competition each pair of participants from the same team became friends.

Your task is to write a program that will find the minimum and the maximum number of pairs of friends that could have formed by the end of the competition.

Input

The only line of input contains two integers n and m, separated by a single space (1 ≤ m ≤ n ≤ ) — the number of participants and the number of teams respectively.

Output

The only line of the output should contain two integers  and  — the minimum possible number of pairs of friends and the maximum possible number of pairs of friends respectively.

Examples

input

5 1

output

10 10

input

3 2

output

1 1

input

6 3

output

3 6

Note

In the first sample all the participants get into one team, so there will be exactly ten pairs of friends.

In the second sample at any possible arrangement one team will always have two participants and the other team will always have one participant. Thus, the number of pairs of friends will always be equal to one.

In the third sample minimum number of newly formed friendships can be achieved if participants were split on teams consisting of 2 people, maximum number can be achieved if participants were split on teams of 1, 1 and 4 people.

Answer key ：

        This is a good math problem , Let's start with a few extreme examples . When m=1 when , The maximum and minimum values are the same , According to the formula, the answer is n*(n-1)/2, The basis of all formulas of this problem is .

        Maximum case ：m-1 There is only one person in each group , There are all the remaining people in the remaining group , Then the answer is (n-m+1)*(n-m)/2, It's better to think .

        In the case of minimum values ： The average distribution is the smallest ,n personal ,m A set of , On average, one group has (n/m) personal , Of course, there will be some missed fish , There may be one more person in some groups （ That is, it cannot be divided ）, And there can only be one more person , At this time, we need to calculate the values of the two separately , And after adding, the final result is . The normal number of groups is (m-n%m) individual , The number of people in each of these groups is (n/m) individual , The rest n%m In the group , The number of people in each group is (n/m+1) individual , Use the general term formula to calculate .

AC Code ：

#include <bits/stdc++.h>
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ll long long
using namespace std;

void solve(){
	ll n,m;
	cin>>n>>m;
	cout<<(m-n%m)*((n/m)*(n/m-1)/2)+(n%m)*(n/m)*(n/m+1)/2<<" "<<(n-m+1)*(n-m)/2;
}
int main()
{
	BUFF;
	int _;
	//cin>>_;
	_=1; 
	while (_--){
		solve();
	}
	return 0;
}

---

B. A and B and Compilation Errors

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

A and B are preparing themselves for programming contests.

B loves to debug his code. But before he runs the solution and starts debugging, he has to first compile the code.

Initially, the compiler displayed n compilation errors, each of them is represented as a positive integer. After some effort, B managed to fix some mistake and then another one mistake.

However, despite the fact that B is sure that he corrected the two errors, he can not understand exactly what compilation errors disappeared — the compiler of the language which B uses shows errors in the new order every time! B is sure that unlike many other programming languages, compilation errors for his programming language do not depend on each other, that is, if you correct one error, the set of other error does not change.

Can you help B find out exactly what two errors he corrected?

Input

The first line of the input contains integer n (3 ≤ n ≤ ) — the initial number of compilation errors.

The second line contains n space-separated integers  (1 ≤  ≤ ) — the errors the compiler displayed for the first time.

The third line contains n - 1 space-separated integers  — the errors displayed at the second compilation. It is guaranteed that the sequence in the third line contains all numbers of the second string except for exactly one.

The fourth line contains n - 2 space-separated integers  — the errors displayed at the third compilation. It is guaranteed that the sequence in the fourth line contains all numbers of the third line except for exactly one.

Output

Print two numbers on a single line: the numbers of the compilation errors that disappeared after B made the first and the second correction, respectively.

Examples

input

5
1 5 8 123 7
123 7 5 1
5 1 7

output

8
123

input

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

output

1
3

Note

In the first test sample B first corrects the error number 8, then the error number 123.

In the second test sample B first corrects the error number 1, then the error number 3. Note that if there are multiple errors with the same number, B can correct only one of them in one step.

Answer key ：

        The title looks frightening , In fact, I said a very simple thing , Three sequences are given , Ask you which element is different between two adjacent sequences , It also ensures that this element is unique and exists , Just record the sum of the three sequences , You can find the different number by subtracting two by two .

AC Code ：

#include <bits/stdc++.h>
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ll long long
using namespace std;

void solve(){
	int n;
	cin>>n;
	ll s1=0,s2=0,s3=0;
	ll x;
	for (int i=0;i<n;i++){
		cin>>x;
		s1+=x;
	}
	for (int i=0;i<n-1;i++){
		cin>>x;
		s2+=x;
	}
	for (int i=0;i<n-2;i++){
		cin>>x;
		s3+=x;
	}
	cout<<s1-s2<<endl<<s2-s3<<endl;
}
int main()
{
	BUFF;
	int _;
	//cin>>_;
	_=1; 
	while (_--){
		solve();
	}
	return 0;
}

---

B. Ilya and Queries

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

Ilya the Lion wants to help all his friends with passing exams. They need to solve the following problem to pass the IT exam.

You've got string s =  (n is the length of the string), consisting only of characters "." and "#" and m queries. Each query is described by a pair of integers ,  (1 ≤  <  ≤ n). The answer to the query ,  is the number of such integers i (  ≤ i < ), that .

Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem.

Input

The first line contains string s of length n (2 ≤ n ≤ ). It is guaranteed that the given string only consists of characters "." and "#".

The next line contains integer m (1 ≤ m ≤ ) — the number of queries. Each of the next m lines contains the description of the corresponding query. The i-th line contains integers ,  (1 ≤  <  ≤ n).

Output

Print m integers — the answers to the queries in the order in which they are given in the input.

Examples

input

......
4
3 4
2 3
1 6
2 6

output

1
1
5
4

input

#..###
5
1 3
5 6
1 5
3 6
3 4

output

1
1
2
2
0

Answer key ：

        This problem was complicated at first , I thought it had to be continuous , In fact, two adjacent ones in the interval are counted as , The way to do this is to take the prefix and array to record the current position before （ Including the current position ） The same number of , The query is the same as the prefix and , Note the scope here ：l≤i＜r, So the answer to prefix and query is sum[r-1]-sum[l-1].

AC Code ： 

#include <bits/stdc++.h>
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ll long long
using namespace std;

const int N=1e5+5;
int sum[N];
void solve(){
	string s;
	cin>>s;
	for (int i=1;i<s.length();i++){
		sum[i]=sum[i-1]+(s[i]==s[i-1]);
	}
	int m;
	cin>>m;
	while (m--){
		int l,r;
		cin>>l>>r;
		cout<<sum[r-1]-sum[l-1]<<endl;
	}
}
int main()
{
	BUFF;
	int _;
	//cin>>_;
	_=1; 
	while (_--){
		solve();
	}
	return 0;
}

---

B. Sereja and Suffixes

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

Sereja has an array a, consisting of n integers . The boy cannot sit and do nothing, he decided to study an array. Sereja took a piece of paper and wrote out m integers  (1 ≤  ≤ n). For each number  he wants to know how many distinct numbers are staying on the positions . Formally, he want to find the number of distinct numbers among .?

Sereja wrote out the necessary array elements but the array was so large and the boy was so pressed for time. Help him, find the answer for the described question for each .

Input

The first line contains two integers n and m (1 ≤ n, m ≤ ). The second line contains n integers  (1 ≤  ≤ ) — the array elements. 

Next m lines contain integers . The i-th line contains integer  (1 ≤  ≤ n).  

Output

Print m lines — on the i-th line print the answer to the number . 

Examples

input

10 10
1 2 3 4 1 2 3 4 100000 99999
1
2
3
4
5
6
7
8
9
10

output

6
6
6
6
6
5
4
3
2
1

Answer key ：

        A very simple recursive problem , We just need to traverse the elements in the array from back to front , If this number already exists then dp The value remains the same , Otherwise, the corresponding dp It's worth adding 1, Finally, just output the answer directly .

AC Code ： 

#include <bits/stdc++.h>
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ll long long
using namespace std;

const int N=1e5+5;
int a[N],dp[N];
bool vis[N];
void solve(){
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	for (int i=n;i>=1;i--){
		if (!vis[a[i]]){
			vis[a[i]]=1;
			dp[i]=dp[i+1]+1;
		}
		else{
			dp[i]=dp[i+1];
		}
	}
	while (m--){
		int l;
		cin>>l;
		cout<<dp[l]<<endl;
	}
}
int main()
{
	BUFF;
	int _;
	//cin>>_;
	_=1; 
	while (_--){
		solve();
	}
	return 0;
}

---

A. Sum of Odd Integers

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

You are given two integers n and k. Your task is to find if n can be represented as a sum of k distinct positive odd (not divisible by 2) integers or not.

You have to answer t independent test cases.

Input

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

The next t lines describe test cases. The only line of the test case contains two integers n and k (1≤n,k≤).

Output

For each test case, print the answer — "YES" (without quotes) if n can be represented as a sum of k distinct positive odd (not divisible by 2) integers and "NO" otherwise.

Example

input

6
3 1
4 2
10 3
10 2
16 4
16 5

output

YES
YES
NO
YES
YES
NO

Note

In the first test case, you can represent 3 as 3.

In the second test case, the only way to represent 4 is 1+3.

In the third test case, you cannot represent 10 as the sum of three distinct positive odd integers.

In the fourth test case, you can represent 10 as 3+7, for example.

In the fifth test case, you can represent 16 as 1+3+5+7.

In the sixth test case, you cannot represent 16 as the sum of five distinct positive odd integers.

Answer key ：

        You should see the question clearly and then do it ！ The title requires different odd numbers and , That is, every odd number can only appear 1 Time , therefore NO The condition of should be n、k Add a sentence to the same condition of parity ：n>k*k（ The result of simplifying the summation formula of the arithmetic sequence ）, Pay attention long long.

AC Code ： 

#include <bits/stdc++.h>
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ll long long
using namespace std;

void solve(){
	ll n,k;
	cin>>n>>k;
	if (n<k*k){
		cout<<"NO"<<endl;
		return;
	}
	if (n&1){
		cout<<(k&1?"YES":"NO")<<endl;
	}
	else{
		cout<<(k&1?"NO":"YES")<<endl;
	}
}
int main()
{
	BUFF;
	int _;
	cin>>_;
	//_=1; 
	while (_--){
		solve();
	}
	return 0;
}

---