Prefix sums(minimums, ...)

ID 30659. The amount on the line

Examples

ID 29638. Quiet Don №3

ID 29640. Quiet don №2

Aksinya loves Gregory, but she is married to Stepan. She is unhappy with her husband, so the time she spends with him can be characterized by a negative indicator of Aksinya's happiness (\(a_i < 0\)), and the time that she spends with Gregory, a positive indicator of happiness (\(a_i > 0\)). It is known that Aksinya spends one day either with her husband or with her lover. 

Examples

ID 29655. tree felling

ID 30699. Gangs of Fomin No. 2

Fomin's gang consists of n groups, each of which has ai people. q raids are planned. The i-th raid will include exactly one robber from each group whose number lies in the segment \([l_i, r_i]\).

Examples

ID 30691. Gangs of Fomin

ID 33256. Cat Goose and random matrix

ID 38139. Enough green

Farmer John's pasture can be thought of as a  NxN grid (\(1<=N<=500\)) of square cells with grass (like a large Chess board). Due to the variability of the soil, the grass in some cells is greener than in others. Each cell (i,j) is described by an integer - the greenness level G(i,j), in the interval \ (1…200\).

Farmer John wants to take a photo of a rectangular sub-grid of his pasture. He wants the minimum of G in his photo to be sharp 100. Help him count how many different pictures he can take. The subgrid can range in size from the entire pasture to one cell. There are \(N^2(N+1)^2/4\) different sublattices, use a 64-bit integer (like < code>long long in C++).

Note that the answer requires a 64-bit integer variable of type long long in C++.

Examples

ID 38384. The choice of flowers for the bouquet

Volodya wants to beautifully congratulate his wife on their wedding anniversary and is going to give her a bouquet of n flowers.

Arriving at a flower shop, Volodya discovered that a bouquet can be made from flowers of m different types, and the number of flowers of each type is not limited. Volodya knows that the first flower of the i-th species in the bouquet makes his wife happier by a_i, and each next flower  
this way she becomes happier on b_i. That is, if in the bouquet x_i > 0 flowers of type i, then flowers of this type make Volodya's wife happier by a_i + (x_i − 1) · b_i.

Like any loving husband, Volodya wants to please his wife as much as possible. Therefore he wants to know by what maximum amount her happiness can increase from a bouquet, picked from the flowers available in the store.

Input data format
The first line contains two integers n and m (1 ≤ n ≤ 10⁹ , 1 ≤ m ≤ 100 000) — required 
the number of flowers in the bouquet and the number of flowers available.
Each of the following m lines describes the i-th kind of flowers and contains two integers a_i and b_i (0 ≤ a_i  , b_i ≤ 10⁹ ) — an increase in happiness from the first flower of the i-th species and an increase in happiness from each subsequent flower of this species.

Output data format
In a single line print a single number — the maximum increase in happiness that Volodya's wife can get from a bouquet of n flowers.
 

Examples

ID 38589. practice test

We have a grid with H rows and W columns. The square in the ith row and jth column will be called Square(i, j). Integers from 1 to H·W are written over the entire grid, and an integer written in Square(i, j) is equal to Ai,j.
You are a wizard and can teleport a shape placed on Square(i, j) to Square(x, y) by spending \(|x-i|+|y-j|\) magiks (magic coins).
Now you need to pass Q practice tests on your abilities as a wizard (sorceress). Ith test will be conducted as follows:
- initially the figure is located in the square, where the integer is written Li;
- Let x be the integer written in the square occupied by the shape. Repeatedly move the shape to the square where the integer x+D is written until x will not become equal to Ri. The test ends when x = Ri .
It is guaranteed that Ri- Li is divisible by D.
For each test, find the sum of magics consumed during that test.

Input
The first line contains three integers: H, W and D (\( 1\leq H,W \leq 300\), \(1 \leq D \leq H \cdot W\)).
The following H lines contain W numbers Ai,j (\(1 \leq A_{i,j} \leq H \cdot W\), \(A_{i,j} \ neq A_{x,y} ((i,j) \neq (x,y))\).
The next line contains an integer Q (\(1 \leq Q \leq 10^5\)).
The last Q lines contain 2 integers each: Li and Ri (\(1 \leq L_i \leq R_i \leq H \cdot W\)), \((R_i-L_i)\) multiple of D.

Imprint
For each test, print the sum of magics spent during this test. The output should be in the order of the tests.
 

ID 39110. Substring length

You have the string s. You want to make a new line, writing each letter in it a number of times equal to the serial number of this letter in the alphabet. For example, s = "abcdc", newline s_new = "abbcccddddccc".  We were wondering what the length of the string will be if you write out all the characters of the original string, starting with the character l and ending with the character r. Total we k requests to you.


Input
In the first line, the program receives as input two numbers n and k (1<=n<=10⁶, 1< ;=k<=10⁶), where n is the string length, k is the number of requests. The second line contains the string s of length n. The next k lines contain the boundaries of the segments l and r (1 <= l <= r <= n). < code>l, r - serial numbers of characters in a string, starting from 1.

Imprint
For each query print the length of the string you got. One number per line. Total k lines.
 

Examples

ID 39356. Get OK

Given a string S of length N, consisting of the characters S, T, O and K. Answer Q requests like the following.
Query i(1 <= i <= Q): for given integers li and r i (1 <= l_i< r_i <= N),  the substring S is considered, starting at index li and ending at index ri < /sub> (both inclusive). You need to determine how many times OK  occurs as a substring in this string?
 

Explanation

ID 39381. Harmonious sequence

A series of lectures at the University of Flatland is devoted to the study of sequences.

The professor calls a sequence of integers \(a_1, a_2, ..., a_n\) harmonious if every number except \(a_1\) and \(a_n\), equals the sum of adjacent:  \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). For example, the sequence [1,2,1,–1]  is harmonic because 2=1+1, and 1=2+(–1) .

Consider sequences of equal length: \(A=[a_1,a_2, ... a_n]\)   and \(B=[b_1,b_2, ... b_n]\). The distance between these sequences will be called the value \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\)  . For example, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2| ++|1–0|+|–1–0|=0+0+1+1=2 \)

At the end of the lecture, the professor wrote on the blackboard a sequence of n integers \(B=[b_1,b_2, ... b_n]\)and asked the students to find harmonious sequence \(A=[a_1,a_2, ... a_n]\) such that \(d( A, B)\) is minimal. To make it easier for himself to check, the professor asks you to write as an answer only the desired minimum distance \(d(A,B)\) .

It is required to write a program that, given a sequence B, determines at what minimum distance from sequence B there is a harmonic sequence A.

Input
The first line of the input file contains the integer n – the number of elements in the sequence ( \(3 \le n \le 300 000\)).

The second line contains n integers \(b_1, b_2, …, b_n (–10^9 \le b_i \le 10^9 )\) .< br />
Imprint
The output file must contain a single integer: the minimum possible distance from the sequence in the input file to a harmonic sequence.

Examples

ID 39482. Subsequence of length L

Given a sequence of N numbers. All its continuous subsequences are considered, in which the number of negative numbers does not exceed C. Find among them a subsequence with the maximum sum, length L. In your answer, indicate the sum of the found subsequence.

Input
The first line contains 3 numbers: the number of numbers N (1 <= N <= 1 000 000),  L and C< /code> (\(1 <= L, C <= N <= 1,000,000\)). Each of the following N lines contain one number, modulo not exceeding 1000.

An example of the organization of source data in the input file (for L = 3 and C = 3):
5 3 3
1
-1
2
-2
3

Several sequences can be selected in this set, but with a maximum sum of 3 it will be: 2+(-2)+3. 
Answer(for С = 3 and L = 3): 3.  ;

 

ID 39574. no time to paint

Besi recently received a set of paints and she wants to paint a long hedge on one side of her pasture. The fence consists of N consecutive 1-meter segments (1≤N≤10⁵). Besi has paints in 26 different colors, which she labeled with letters from 'A' to Z' in ascending order of darkness ('A' is the lightest color, 'Z' is the darkest). Therefore, it can describe the coloring of the hedge as a string of N characters (where each character is one of - from 'A' to Z').
Initially, all segments of the fence are not painted. Besi can paint any continuous range of segments with a single color with a single brush stroke, and she never paints a lighter over a darker one (she can paint a darker over a lighter one).

For example, she can color an initially unpainted segment of length 4 like this:

.... -> BBB. -> BBLL-> BQQL
Limited in time, Besi may leave some consecutive segments unpainted. She is now looking at Q line segment candidates (1≤Q≤10⁵), each given by two integers (a,b) (1≤a≤b≤N) indicating the indexes of the segment endpoints that should stay unpainted.

For each candidate, specify the minimum number of touches required to color all segments outside that range with the desired color, leaving segments inside the range uncolored. Note that Besi doesn't actually color anything, so the answers for each candidate range are independent.

Input
The first line contains N and Q.
The next line contains N representing the desired color for each hedge segment.

Each of the next Q lines contains two space-separated integers a and b representing a range of segments that may not be colored.

Imprint
For each of the Q candidates print the answer on a new line.

Examples

8 2
ABBAABCB
3 6
14

ID 39671. Substrings in a string

Given a string S = s₁s₂...s_n and a set of queries like (l₁, r ₁, l₂, r₂). For each query, it is required to answer whether the substrings s_l1...s_r1 and s_l2...s_{r2 are equal} .


Input:
The first line contains the string S (1 <= |S| <= 10⁵) consisting of lowercase Latin letters. 
The second line contains a natural number q (1 <= q <= 10⁵) - the number of requests.
The next q lines contain 4 natural numbers each - l₁, r₁, l₂, r₂ ( 1 <= l₁ <= r₁ <= |S|, 1 <=l₂ <= r< sub>2 <= |S|).

Output:
For each query, print '+' if the substrings are equal, and '-' otherwise.

Examples:
 

ID 39672. Tom Sawyer and the word on the fence

While painting the fence, Tom Sawyer wrote the word s on it. However, he then decided that palindrome words looked prettier.
Now he wants to add another word g to the given word s on the right so that the resulting word sg is a palindrome. However, in order to save paint, the length g should be as short as possible.
Help Tom Sawyer identify the word g.

Input:
The first line contains the word s (1 <= |s| <= 200000) consisting of lowercase Latin letters.

Output:
Print the minimum possible length of the word g that needs to be completed so that the word sg on the fence becomes a palindrome. If you don't need to add anything, then print '-'.

Examples:
 

ID 39673. Reading aloud

Tom Sawyer and Huckleberry Finn read a newspaper clipping aloud together. But it so happened that Tom Sawyer began to read from the i-th character, and Huckleberry Finn from the j-th. 
How many letters can they read before they find they started from different places, or until they both read to the end?

Input:
The first line contains the string S (1 <= |S| <= 10⁵), consisting of lowercase Latin letters - an inscription from a newspaper clipping.
The next line contains a natural number q - the number of requests.
The next q lines contain two natural numbers i and j each - the positions from which Tom Sawyer and Huckleberry Finn start reading, respectively.

Output:
Print q lines, each of which should contain one integer - the number of characters that match when reading substrings starting with the i-th and j-th characters.

Examples:
 

ID 39674. Huckleberry Finn and two strings

Huckleberry Finn has two strings s and t of the same length n.
Huckleberry Finn likes strings to have the same prefixes (beginnings), so he can swap two characters in string s to make the common prefix of strings s and t larger.
However, this trick is rather tedious, so Huckleberry Finn will either not do it at all, or will do it exactly once.

Help Huckleberry Finn determine the longest common prefix length of strings s and t that he can get.


Input:
The first line contains a natural number n (1 <= n <= 200000) - the length of strings s and t
The second line contains a string s, consisting of lowercase Latin letters.
The third line contains a string t consisting of lowercase Latin letters.

Output:
Print one natural number - the maximum length of the common prefix s and t, which can be obtained by exchanging two characters in the string s at most once.

Examples:
 

ID 39675. cultural contact

At the beginning of the 18th century, a group of European explorers arrived on an island inhabited by a group of tribes that had never come into contact with representatives of European civilization.

To successfully establish contacts with the natives, the leader of the group plans to give a gift to the leader of each tribe he meets. To this end, he brought a long chain of glass, similar to precious stones. 
Let's represent the string as a string s, consisting of small letters of the English alphabet, where each letter means the type of piece of glass at the corresponding position. 
The researchers are going to cut the chain into some fragments, and then hand over exactly one fragment to the leader of each tribe encountered by the group. The research leader decided to split the chain into fragments according to the following rules:

• In order not to spend a lot of time on cutting, each fragment should be a group of adjacent pieces of glass in the chain, that is, a substring of the string s.
• All pieces of glass must be used, that is, each piece of glass must be included in exactly one fragment.
• Because the researchers don't know how the aborigines will value certain types of glass, they want each chief to get the same set of glass without regard to order. In other words, for any type of glass, the number of glass of this type must be the same in each of the fragments.
• Researchers don't know how many tribes live on the island, so the number of prepared fragments should be as large as possible.

ID 39964. Maximum Questions

Max had two strings s of length n and t of length m written in her notebook, consisting of the letters "a"; and "b" Latin alphabet. Moreover, Max knows that the string t has the form «abab...», that is, the letter «a» is on the odd positions of the string, and the letter — "b".

Suddenly, in the morning, Max discovered that someone had messed up her string s. Some of the s's have been changed to "?".

Let's call the sequence of positions i, i + 1, ..., i + m - 1 an occurrence of string t in s, if 1 ≤ i ≤  n - m + 1 and t₁ = s_i, t₂&thinsp ;= s_i + 1, ..., t_m = s_{i +  m - 1}.

The beauty of string s is measured as the maximum number of non-overlapping occurrences of string t in it. Max can replace some of the "?" on "a" or "b" (characters in different positions can be replaced by different letters). Max wants to make substitutions so that the beauty of the string s is as large as possible. Of all these options, she wants to replace as few "?" characters as possible. Find out how many substitutions she has to make.

Input:
The first line contains a single integer n (1 ≤ n ≤ 10⁵) — string length s.
The second line of the input contains a string s of length n, consisting only of the letters "a"; and "b" the Latin alphabet, as well as the symbols «?».
The third line contains the integer m (1 ≤ m ≤ 10⁵) — string length t. The string t itself contains "a"; in odd positions, and "b" on even numbers.

Output:
Print a single integer — the minimum number of substitutions that Vasya must make in order to make the beauty of the string s the maximum possible.

Examples:
 

ID 41228. XOR and favorite number

Evan has a favorite number k and an array a_i of length n. Now it asks you to answer m requests.

For each query given by a pair of numbers l and r, it is required to find the number of pairs of integers i and j such that l ≤ i ≤ j ≤ r and xor of numbers a_i , a_i + 1, ..., a_j is k.

Input:
The first line contains integers n, m and k (1 ≤ n, m ≤ 10⁵, 0 ≤ k ≤  10⁶) — the length of the array, the number of requests, and Evan's favorite number, respectively.
The second line contains n integers ai (0 ≤ a_i ≤ 10⁶) — Evan's array.
Then there are m lines. The i-th line contains numbers l_i and r_i (1 ≤ l_i ≤ r< sub>i ≤ n) defining the i-th query.

Output:
Print m lines, the answers to the questions in the order they appear in the input.

Examples:
 

ID 43124. Binary sort

You have decided to visit your friend from Ozersk. However, at the entrance to the city, you were stopped and asked to solve a problem to make sure that you can actually drive into the territory of the closed city.
A binary string is a string consisting only of the characters 0 and 1. The police officer gave you the binary string s₁s₂ ... s_n. You need to sort this string (that is, turn it into a string like  00 ... 0011 ... 11) in the least number of operations. In one operation, you can do the following:
x Pick an arbitrary index in row 1 <= i <= n;
x For all j >= i, change the value in the jth position to the opposite, that is, if s_j = 1, then make s_j = 0, and vice versa.

Input
Each test consists of several sets of input data. The first line contains an integer t (1 <= t <= 10⁴) the number of test cases. The following is a description of the input datasets.
The first line of each test case contains a single integer n (1 <= n <= 10⁵) the length of the string.
The second line of each test case contains a binary string s of length n.
It is guaranteed that the sum of n over all test cases does not exceed 2 ·10⁵.

Imprint
For each test case, print a single integer, the minimum number of operations that need to be done to sort the string.
 

Examples

ID 43720. Darts

Petya and Vanya decided to come up with their own rules for playing Darts. They took a round playing field and divided it into sectors. Sectors are numbered with natural numbers. Each sector was assigned the number of points that can be obtained if you hit it with a dart. Before the start of the game, a zero sector is selected, which serves as a reference point: the number of points that a player scores when entering a sector is calculated as the number of points indicated in the sector multiplied by the distance (number of sectors) from the zero sector. When hitting the zero sector, the number of points is equal to zero.

Since it is not known in advance which sectors the players will fall into, the zero sector should be chosen so that the player scores the maximum number of points if he hits all sectors of the playing field once.

Determine which sector you want to choose zero.


Input
The first line of the input contains the number N — the number of sectors into which the playing field is divided.
The following N lines each contain a single number — the number of points that players gain by getting into the corresponding sector, starting from sector number 1.

Imprint
Print one number — sector number to be selected as zero.
 

Examples

ID 43721. Two garbage trucks

Garbage containers are installed at every kilometer of the two-way ring road. The length of the ring road is N kilometers. The zero kilometer and the Nth kilometer of the road are at the same point. The amount of garbage that accumulates daily in each of the containers is known.
There are two garbage trucks on the road. One goes clockwise, the other against. Both garbage trucks leave the recycling center at the same time towards each other and meet near one of the containers. Only one garbage truck can take out garbage from one container. The garbage delivery time is calculated as the product of the amount of garbage by the distance from the point to the recycling center. The waste recycling center was opened in one of the garbage collection points in such a way that the total time for garbage collection by two garbage trucks was minimal.
Determine which container number you need to place a recycling center in order to minimize the time for garbage trucks to collect garbage.

Input
The first line of the input contains number N (1 <= N <= 10,000,000) – the number of garbage collection points on the ring road. Each of the following N lines contains a number of – the amount of garbage in the container (all numbers are natural, the amount of garbage in each point does not exceed 1000). The numbers are given in order of containers on the motorway, starting from the first kilometer.

Imprint
Display one number on the screen - the answer to the problem.
 

Examples

ID 43722. Continuous subsequence

Given a sequence of N natural numbers. It is known that the sum of all numbers in the sequence does not exceed 10⁹. All its continuous subsequences are considered, in which the number of odd numbers is a multiple of K = 7. Find the largest sum of such a subsequence. 

Input
The first line of the input contains a single number N (1 <= N <= 1 000 000) -  number of numbers. Each of the following N lines contains one natural number not exceeding 1000.
 
Input
Print the answer to the problem