A sequence a1,a2,…,an is called good if, for each element ai, there exists an element aj (i≠j) such that ai+aj is a power of two (that is, 2d for some non-negative integer d). For example, the following sequences are good: [5,3,11] (for example, for a1=5 we can choose a2=3. Note that their sum is ...

Polycarp likes numbers that are divisible by 3. He has a huge number s. Polycarp wants to cut from it the maximum number of numbers that are divisible by 3. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after m such cuts, there will be m+1 ...

You are given a permutation p1,p2,…,pn. A permutation of length n is a sequence such that each integer between 1 and n occurs exactly once in the sequence. Find the number of pairs of indices (l,r) (1≤l≤r≤n) such that the value of the median of pl,pl+1,…,pr is exactly the given number m. The media...

Polycarp has n coins, the value of the i-th coin is ai. Polycarp wants to distribute all the coins between his pockets, but he cannot put two coins with the same value into the same pocket. For example, if Polycarp has got six coins represented as an array a=[1,2,4,3,3,2], he can distribute the coi...

You are given three integers a, b and x. Your task is to construct a binary string s of length n=a+b such that there are exactly a zeroes, exactly b ones and exactly x indices i(where 1≤i<n)such that si≠si+1. It is guaranteed that the answer always exists. For example, for the string “01010” the...

The heat during the last few days has been really intense. Scientists from all over the Berland study how the temperatures and weather change, and they claim that this summer is abnormally hot. But any scientific claim sounds a lot more reasonable if there are some numbers involved, so they have dec...

Polycarp has n coins, the value of the i-th coin is ai. It is guaranteed that all the values are integer powers of 2 (i.e. ai=2d for some non-negative integer number d). Polycarp wants to know answers on q queries. The j-th query is described as integer number bj. The answer to the query is the min...

Sonya decided that having her own hotel business is the best way of earning money because she can profit and rest wherever she wants. The country where Sonya lives is an endless line. There is a city in each integer coordinate on this line. She has n hotels, where the i-th hotel is located in the c...

Sonya decided to organize an exhibition of flowers. Since the girl likes only roses and lilies, she decided that only these two kinds of flowers should be in this exhibition. There are n flowers in a row in the exhibition. Sonya can put either a rose or a lily in the i-th position. Thus each of n p...

Since Sonya is interested in robotics too, she decided to construct robots that will read and recognize numbers. Sonya has drawn n numbers in a row, ai is located in the i-th position. She also has put a robot at each end of the row (to the left of the first number and to the right of the last numb...

Mishka started participating in a programming contest. There are n problems in the contest. Mishka’s problem-solving skill is equal to k. Mishka arranges all problems from the contest into a list. Because of his weird principles, Mishka only solves problems from one of the ends of the list. Every t...

A string s of length n can be encrypted by the following algorithm: iterate over all divisors of n in decreasing order (i.e. from n to 1), for each divisor d, reverse the substring s[1…d] (i.e. the substring which starts at position 1 and ends at position d). For example, the above algorithm appl...

You are given a string s consisting of n lowercase Latin letters. Polycarp wants to remove exactly k characters (k≤n) from the string s. Polycarp uses the following algorithm k times: if there is at least one letter ‘a’, remove the leftmost occurrence and stop the algorithm, otherwise go to next it...

There are n cities and m roads in Berland. Each road connects a pair of cities. The roads in Berland are one-way. What is the minimum number of new roads that need to be built to make all the cities reachable from the capital? New roads will also be one-way. Input The first line of input consist...