Segment tree, RSQ, RMQ

ID 33700. Sums on subsegments

Implement a data structure to efficiently calculate the sums of consecutive array elements.

Input
The first line contains one natural number N (1 ≤ N ≤ 100000) — the number of numbers in the array.

The second line contains N numbers from 1 to 100000 — array elements.

The third line contains one natural number K (1 ≤ K ≤ 30000) — the number of requests to calculate the amount.

The next K lines contain two numbers — the numbers of the left and right elements of the array segment (it is assumed that the elements of the array are numbered from one).'

Imprint
For each query print the sum of the numbers of the corresponding section of the array. Print the numbers in one line separated by a space.
 

ID 33701. Error

Implement an efficient data structure that allows you to modify array elements and calculate the GCD of several consecutive elements.

Input
The first line contains one natural number N (1 ≤ N ≤ 100000) — the number of numbers in the array.
The second line contains N numbers from 0 to 100000 — array elements.
The third line contains one natural number M (1 ≤ M ≤ 30000) — number of requests.
Each of the next M lines is a description of the request. First, a single letter is entered that encodes the type of request (s — compute GCD, u — update element value).
The s is followed by two numbers — numbers of the left and right borders of the segment.
The u is followed by two numbers — the element number and its new value.

Imprint
For each query s print the result. Print all numbers on one line separated by spaces.
 

ID 33699. Maximums on subsections

Implement a data structure to efficiently calculate the maxima of consecutive array elements.

Input
The first line contains one natural number N (\(1 <= N <= 100000\)) — the number of numbers in the array. The second line contains N numbers from 1 to 100000 — array elements. The third line contains one natural number K (\(1 <= K <= 30000\)) &mdash ; the number of requests to calculate the maximum. In the following K lines, enter two numbers each — the numbers of the left and right elements of the array segment (it is assumed that the elements of the array are numbered from one).

Imprint
For each query, print the value of the maximum element in the specified range of the array. Output the numbers in one line separated by a space.

Examples

ID 38136. Farmer John's Cow Organization 2

A delegation (1≤N≤2⋅10⁵) is selected from N cows. They stand in a row, cow i has breed b_i.

The delegation will consist of a continuous segment of at least three cows, i.e. cows l…r for integers l and r satisfying the conditions 1≤l<r≤N and r−l≥2. Three cows in the selected interval are marked as leaders of the delegation. Two boundary cows must be leaders. In addition, each leader must have a different breed from all other cows in the delegation (leaders or non-leaders).

Determine the number of ways in which a delegation can be selected. Two delegations are considered different if they have different members or leaders.

Input: 
The first line contains N.
The second line contains N integers b₁,b₂,…,b_N, each in the interval [1,N].
Output: 
The number of possible delegations on one line.

Examples

ID 38473. weighing stones

Jack found N stones and arranged them in order of increasing mass. The masses of all stones are different. The lightest stone was number 1, the next ≤ 2 and so on, the heaviest one was numbered N.

Jack has a scale and decided to put all the stones on it in some order. The order in which he will place the stones is known, and which stone will land on which bowl.

Your task — determine the state of the scales after adding each stone. The exact weights of the stones are not known — only their numbers are given.

Input
The first line contains the integer N (1  N ≤ 100000).

Each of the next N lines contains two integers: R (1 ≤ R ≤ N) and S (1 ≤ S ≤ 2). R is the number of the stone that will be placed on the bowl S. All Rs will be different.

Imprint
Output N lines -  one for each stone. If bowl 1 is heavier after adding the corresponding stone, print “<”. If side 2 is heavier, print “>”. If it is impossible to determine what state the scales will be in, print “?”.

Examples

<
>
>
?
>

ID 38509. Substrings of subsequences

Let's call a subsequence of array a a non-empty array b such that it can be obtained from array a by deleting some (possibly none) elements of array a. For example, array [1,3]  is a sequence of array [1,2,3] , but [3,1]  is not.

Let's call a subsegment of array a a non-empty array b such that it can be obtained by deleting several (possibly none) of the first and last elements of array a. For example, [1,2]  is a subsegment of the array [1,2,3] , but [1,3]  is not. It is easy to see that an array of length n has exactly  \( {n(n+1) \over 2}\)  subsegments.

Let's call an array a of length n increasing if for any 1 ≤ i≤ n a_i ≤ a_i+1.

The monotonicity of an array is the number of its increasing subsegments.

Given an array a of length n. Calculate the sum of monotonicities over all its subsequences. Since the answer can be very large, print it modulo 10⁹+7.

Input
The first line contains an integer n (1 ≤ n ≤ 200000) — array length a.
The second line contains n integers (1 ≤ a_i ≤ 200000) — array elements a.

Imprint
Print a single integer — the sum of the monotonicities of all subsequences modulo 10⁹+7.

Note
In the first test case, the array has 7 subsequences:

• Array [1]  has exactly one subsegment and is ascending.
• The array [2]   has exactly one subsegment and is increasing.
• The array [3]  has exactly one subsegment and is increasing.
• The array [1,2]  has three subsegments ([1], [2], [1,2] ) and they are all increasing.
• The array [1,3]  has three subsegments ([1], [3], [1,3] ) and they are all increasing.
• The array [3,2]   has three subsegments ([3], [2], [3, 2] ), but only two of them ([3]  and [2] ) are ascending.
• The array [1,3,2]  has six subsegments ([1], [3], [2], [1,3], [3,2], [1,3,2] ) and four of them ([1], [3], [2], [1,3] ) are increasing.

Examples

ID 38511. Journey along the line

Let's say that the sequence of strings t₁ , ..., t_k is a journey of length k if for all i > 1 t<sub>i< /sub> is a substring of ti - 1 of strictly less length. For example, { ab , b } is a journey, and { ab , c } or { a , a } — no.

Define a string traversal s as a traversal t1 , ..., tk , all of whose strings can be nested in s such that there are (possibly empty) strings u1 , ..., uk + 1 such that s = u1t1 u2 t2 ... uk tk uk +&thinsp ;1 . For example, { ab , b } is a string travel for abb , but not for bab , since the corresponding substrings are from right to left.

Let's call the length of the journey the number of lines of which it consists. Determine the maximum possible travel length along the given string s .

Input
The first line contains an integer n ( 1 ≤ n ≤ 500 000 ) — length of string s .

The second line contains the string s , consisting of n lowercase English letters.

Imprint
Print one number — the longest travel length in string s .

Note
In the first example, the longest string traversal is { abcd , bc , c } .

In the second example, { bb , b } would be appropriate.</sub>

Examples

ID 39839. hidden treasures

The daughter of the King of Flatland is about to marry Prince Charming. 
The prince wants to give the princess treasures, but he is not sure which diamonds to choose from his collection.

There are n diamonds in the prince's collection, each characterized by weight w_i and value v_i. 
The prince wants to give the most expensive diamonds, but the king is smart and will not accept diamonds with a total weight of more than R. On the other hand, the prince will consider himself greedy for the rest of his life if he gives diamonds with a total weight of less than L.

Help the prince choose a set of diamonds with the highest total value so that the total weight is in the segment [L, R].

Input:
The first line contains the number n (1 <= n <= 32), L and R (0 <= L <= R <= 10¹⁸).
The next n lines describe the diamonds and contain two numbers each - the weight and value of the corresponding diamond (1 <= wi, vi <= 10¹⁵).

Output:
The first line of the output should contain k - the number of diamonds to give to the princess. 
The second line should contain the numbers of the diamonds to be given.
Diamonds are numbered from 1 to n in the order they appear in the input.

If it is impossible to compose a present for the princess, then print 0 in the first line of the output.

Examples:
 

ID 39961. Sum of lows

You are given an array of n integers. You need to divide it into k non-empty subsegments (a sequence of consecutive elements) so that:
1) Each element of the array was included in exactly one subsegment.
2) If for each subsegment we choose the minimum number in it, then the sum of all minima should be the maximum possible.

Report the sum of the minima of the values ​​in the subsegments of this partition.

Input:
The first line contains two natural numbers - n (1 <= n <= 500) and k (1 <= k <= n).
The second line contains n integers - the elements of the array a_i (1 <= a_i <= 10⁵).

Output:
Print one number - the answer to the problem.

Example:
 

ID 41229. Inversions on a segment

Given a permutation of n elements.
Answer m queries about the number of inversions for a permutation subsegment from l to r.
An inversion is a pair of indices i, j such that i < j and a_i > a_j, where a_i is the i-th element of the permutation.

Input:
The first line contains the number n (1 <= n <= 10⁵).
The second line contains a permutation of n elements (the elements of the permutation are pairwise distinct integers from 1 to n).
The third line contains number m (1 <= m <= 10⁵).
The next m lines contain two integers l and r - the bounds of the query (1 <= l, r <= n).

Output:
Print m lines - the answers to these queries.

Examples: