Located on a line are N segments, numbered from 0 to N − 1, whose positions are given in arrays A and B. For each I (0 ≤ I < N) the position of segment I is from A[I] to B[I] (inclusive). The segments are sorted by their ends, which means that B[K] ≤ B[K + 1] for K such that 0 ≤ K < N − 1.

Two segments I and J, such that I ≠ J, are overlapping if they share at least one common point. In other words, A[I] ≤ A[J] ≤ B[I] or A[J] ≤ A[I] ≤ B[J].

We say that the set of segments is non-overlapping if it contains no two overlapping segments. The goal is to find the size of a non-overlapping set containing the maximal number of segments.

For example, consider arrays A, B such that:

A[0] = 1 B[0] = 5
A[1] = 3 B[1] = 6
A[2] = 7 B[2] = 8
A[3] = 9 B[3] = 9
A[4] = 9 B[4] = 10
The segments are shown in the figure below.



The size of a non-overlapping set containing a maximal number of segments is 3. For example, possible sets are {0, 2, 3}, {0, 2, 4}, {1, 2, 3} or {1, 2, 4}. There is no non-overlapping set with four segments.

Write a function:

def solution(A, B)

that, given two arrays A and B consisting of N integers, returns the size of a non-overlapping set containing a maximal number of segments.

For example, given arrays A, B shown above, the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..30,000];
each element of arrays A and B is an integer within the range [0..1,000,000,000];
A[I] ≤ B[I], for each I (0 ≤ I < N);
B[K] ≤ B[K + 1], for each K (0 ≤ K < N − 1).

Pour un tableau donné A de N entiers et une suite S de N entiers de l'ensemble {−1, 1}, on définit val(A, S) comme suit :

val(A, S) = |somme{ A[i]*S[i] pour i = 0..N−1 }|

(Supposons que la somme de zéro élément est égale à zéro.)

Pour un tableau A donné, on cherche une telle suite S qui minimise val(A,S).

Écrivez une fonction :

def solution(A)

qui, étant donné un tableau A de N entiers, calcule la valeur minimale de val(A,S) à partir de toutes les valeurs possibles de val(A,S) pour toutes les séquences possibles S de N entiers de l'ensemble {−1, 1}.

Par exemple, tableau donné :

A[0] = 1
A[1] = 5
A[2] = 2
A[3] = -2
votre fonction doit retourner 0, puisque pour S = [−1, 1, −1, 1], val(A, S) = 0, qui est la valeur minimale possible.

Ecrire un algorithme efficace pour les hypothèses suivantes :

N est un nombre entier dans la plage [0..20 000] ;
chaque élément du tableau A est un entier compris dans l'intervalle [−100..100].

You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1,
max counter − all counters are set to the maximum value of any counter.
A non-empty array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
if A[K] = N + 1 then operation K is max counter.
For example, given integer N = 5 and array A such that:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4
the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)
The goal is to calculate the value of every counter after all operations.

Write a function:

def solution(N, A)

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4
the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000];
each element of array A is an integer within the range [1..N + 1].

Un tableau A non vide composé de N entiers est donné. Une paire d'entiers (P, Q), telle que 0 ≤ P < Q < N, est appelée une tranche du tableau A (notez que la tranche contient au moins deux éléments). La moyenne d'une tranche (P, Q) est la somme de A[P] + A[P + 1] + ... + A[Q] divisée par la longueur de la tranche. Pour être précis, la moyenne est égale à (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).

Par exemple, tableau A tel que :

A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8
contient les exemples de tranches suivants :

tranche (1, 2), dont la moyenne est (2 + 2) / 2 = 2 ;
tranche (3, 4), dont la moyenne est (5 + 1) / 2 = 3 ;
tranche (1, 4), dont la moyenne est (2 + 2 + 5 + 1) / 4 = 2,5.
Le but est de trouver la position de départ d'une tranche dont la moyenne est minimale.

Écrivez une fonction :

classe Solution { public int solution(int[] A); }

qui, étant donné un tableau A non vide composé de N entiers, renvoie la position de départ de la tranche avec la moyenne minimale. S'il y a plus d'une tranche avec une moyenne minimale, vous devez renvoyer la plus petite position de départ d'une telle tranche.

Par exemple, étant donné le tableau A tel que :

A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8
la fonction doit renvoyer 1, comme expliqué ci-dessus.

Ecrire un algorithme efficace pour les hypothèses suivantes :

N est un nombre entier dans la plage [2..100 000] ;
chaque élément du tableau A est un entier compris dans l'intervalle [−10 000..10 000].