Bạn được cung cấp danh sách phát (playlist) của một đài phát thanh kể từ khi thành lập. Danh sách này gồm tổng cộng n bài hát.

Nhiệm vụ của bạn là tìm độ dài của dãy liên tiếp dài nhất trong playlist sao cho mỗi bài hát trong dãy đều là duy nhất (không bị lặp).

Dữ liệu vào:

Dòng đầu tiên chứa một số nguyên n — số lượng bài hát.

Dòng thứ hai chứa n số nguyên k1, k2, ..., k_n — mã số (ID) của từng bài hát.

Dữ liệu ra:

In ra một số nguyên duy nhất: độ dài của dãy liên tiếp dài nhất mà tất cả các bài hát đều không trùng lặp.

Ràng buộc:

~1 \le n \le 2 \cdot 10^5~

~1 \le k_i \le 10^9~

Ví dụ :

Input:

8
1 2 1 3 2 7 4 2

Output:

5

Cho dãy số nguyên dương A và hai số L, R.

Hãy đếm số lượng đoạn con liên tiếp có tổng nằm trong đoạn [L, R] (tức là >= L và <= R).

Input:

• Dòng 1: N, L, R.

• Dòng 2: N số nguyên A[i].

Giới hạn:

• 1 <= N <= 10^5

• 1 <= L <= R <= 10^14

• 1 <= A[i] <= 10^9

Output:

• Số lượng đoạn con thỏa mãn.

Ví dụ 1:

Input:

3 2 4
1 2 3

Output:

3

Ví dụ 2:

Input:

4 5 10
1 2 3 4

Output:

6

Cho một mảng A gồm N số nguyên và Q truy vấn. Mỗi truy vấn gồm 3 số (L, R, X). Với mỗi truy vấn, hãy đếm xem số X xuất hiện bao nhiêu lần trong đoạn A[L...R].

Gợi ý:

Cách 1 (Nếu N*Q nhỏ): Dùng O(N) cho mỗi truy vấn.

Cách 2 (Nếu N, Q lớn, nhưng giá trị A[i] nhỏ): Xây dựng mảng cộng dồn cho từng giá trị. P[X][i] = số lần X xuất hiện trong A[1...i].

Cách 3 (Nếu N, Q lớn, A[i] lớn): Dùng map<int, vector<int>> lưu các vị trí.

Ràng buộc (dùng cách 2):

1 <= N, Q <= 10^5

1 <= A[i] <= 100 (Giá trị A[i] nhỏ)

Input:

Dòng đầu tiên chứa N.

Dòng thứ hai chứa N số A[i] (1 <= A[i] <= 100).

Dòng thứ ba chứa Q.

Q dòng tiếp theo, mỗi dòng chứa L, R, X (1 <= L <= R <= N, 1 <= X <= 100).

Output:

In Q dòng, mỗi dòng là kết quả cho 1 truy vấn.

Ví dụ:

Input:

10
1 2 3 1 2 3 1 2 3 1
3
1 10 1
3 8 2
5 5 5

Output:

4
2
0

Cho một mảng A gồm N số nguyên (có thể âm). Tìm đoạn con A[L...R] có tổng lớn nhất.

Gợi ý (Dùng mảng cộng dồn): Tong(L..R) = P[R] - P[L-1]. Ta cần tìm max(P[R] - P[L-1]) với L <= R. Khi duyệt R từ 1 đến N, ta cần tìm P[L-1] nhỏ nhất (với L-1 < R). Hãy duy trì một biến minprefix (là P[L-1] nhỏ nhất đã gặp) khi duyệt. KetQua = max(KetQua, P[R] - minprefix)

Input:

Dòng đầu tiên chứa N (1 <= N <= 10^5).

Dòng thứ hai chứa N số A[i] (-10^9 <= A[i] <= 10^9).

Output:

In ra tổng lớn nhất.

Ví dụ:

Input:

8
-1 2 4 -3 5 2 -5 2

Output:

10

Cho mảng A (N số) và số K. Tìm hai đoạn con không giao nhau và đều có độ dài K sao cho tổng của chúng là lớn nhất. (Tức là tìm i, j sao cho [i, i+K-1] và [j, j+K-1] không giao nhau, và Tong(i...i+K-1) + Tong(j...j+K-1) là lớn nhất).

Gợi ý:

Dùng mảng cộng dồn tính TongK[i] = tổng của đoạn K phần tử kết thúc tại i.

Xây dựng mảng MaxLeft[i] = tổng K lớn nhất trong đoạn [1, i].

Xây dựng mảng MaxRight[i] = tổng K lớn nhất trong đoạn [i, N].

Duyệt i từ 1 đến N-K. Kết quả = max(MaxLeft[i] + MaxRight[i+K]).

Input:

Dòng đầu tiên chứa N và K (2*K <= N <= 10^5).

Dòng thứ hai chứa N số A[i] (1 <= A[i] <= 1000).

Output:

In ra tổng lớn nhất của hai đoạn K.

Ví dụ:

Input:

8 2
1 5 2 4 8 1 3 2

Output:

19

Giải thích:

Đầu vào: N = 8, K = 2 Mảng A: [1, 5, 2, 4, 8, 1, 3, 2]

Liệt kê tất cả các đoạn con (dài 2) và tổng của chúng:

Đoạn 1 (vị trí 1, 2): [1, 5] ➜ Tổng = 6

Đoạn 2 (vị trí 2, 3): [5, 2] ➜ Tổng = 7

Đoạn 3 (vị trí 3, 4): [2, 4] ➜ Tổng = 6

Đoạn 4 (vị trí 4, 5): [4, 8] ➜ Tổng = 12

Đoạn 5 (vị trí 5, 6): [8, 1] ➜ Tổng = 9

Đoạn 6 (vị trí 6, 7): [1, 3] ➜ Tổng = 4

Đoạn 7 (vị trí 7, 8): [3, 2] ➜ Tổng = 5

Tìm cặp tốt nhất không giao nhau:

Đoạn tốt nhất (Lớn nhất): Đoạn [4, 8] (vị trí 4, 5) có tổng là 12.

Đoạn tốt nhất còn lại (Không giao):

Vì ta đã chọn đoạn ở vị trí 4 và 5, chúng ta không được chọn bất kỳ đoạn nào khác chạm vào vị trí 4 hoặc 5.

Ta phải loại:

[2, 4] (vì chạm vị trí 4)

[8, 1] (vì chạm vị trí 5)

Các lựa chọn còn lại của chúng ta là:

[1, 5] (Tổng 6)

[5, 2] (Tổng 7)

[1, 3] (Tổng 4)

[3, 2] (Tổng 5)

Trong số này, đoạn tốt nhất là [5, 2] với tổng là 7.

Kết quả: Tổng của hai đoạn tốt nhất không giao nhau là: 12 + 7 = 19.

Cho mảng A[] gồm N phần tử, mảng B gồm M phần tử. Nhiệm vụ của bạn là xác định xem B có phải là một mảng con (không cần liên tiếp nhưng cần giữ đúng thứ tự các phần tử) của mảng A.

Ví dụ mảng A[] = {1, 1, 2, 8, 9, 3, 4}, B[] = {1, 2, 9, 4} là một mảng con của mảng A

Đầu vào

Dòng đầu tiên gồm N và M

Dòng thứ 2 gồm N số A[i]

Dòng thứ 3 gồm M số B[i]

Giới hạn

1<=N,M<=10^6

1<=A[i],B[i]<=10^6

Đầu ra

In ra YES nếu B là mảng con của A, ngược lại in NO.

Ví dụ :

Input 01

16 2
3 6 10 10 10 2 8 4 2 1 9 4 2 1 6 3 
2 3

Output 01

YES

Cho một xâu s chỉ gồm các kí tự '. Và '#', có độ dài n (2 <= n <= 10^5). Cho m truy vẫn dạng l[i], r(i] (1 <= l[i] < r[i] <= n). Bạn cần tính kết quả của truy vấn là số lượng các giá trị k (l[i] <= k < r[i]) thỏa mãn s[k] = s[k + 1].

Định dạng đầu vào:

Dòng đầu tiên là xâu s.

Dòng thứ 2 là số nguyên m - số truy vấn.

m dòng tiếp theo, dòng thứ i chứa 2 số nguyên l[i] và r[i].

Định dạng đầu ra: Gồm m dòng là kết quả của m truy vấn.

Input 01:

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

Output 01:

1
1
5
4

Input 02:

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

Output 02:

1
1
2
2
0

Cho một mảng A gồm N số nguyên dương và một số K. Tìm đoạn con A[L...R] có độ dài (R-L+1) lớn nhất sao cho tổng của đoạn đó không vượt quá K.

Input:

Dòng đầu tiên chứa N và K (1 <= N <= 10^5, 1 <= K <= 10^9).

Dòng thứ hai chứa N số A[i] (1 <= A[i] <= 10^4).

Output:

In ra độ dài lớn nhất tìm được. Nếu không có đoạn nào, in 0.

Ví dụ:

Input:

8 20
1 3 5 1 2 4 1 9

Output:

7

(Giải thích: Đoạn A[1...7] = 1+3+5+1+2+4+1 = 17 (<= 20). Đây là đoạn dài nhất (dài 7).)

Cho một mảng A gồm N số nguyên dương và một số K. Tìm đoạn con A[L...R] có độ dài (R-L+1) ngắn nhất sao cho tổng của đoạn đó lớn hơn hoặc bằng K.

Input:

Dòng đầu tiên chứa N và K (1 <= N <= 10^5, 1 <= K <= 10^9).

Dòng thứ hai chứa N số A[i] (1 <= A[i] <= 10^4).

Output:

In ra độ dài ngắn nhất tìm được. Nếu không có đoạn nào, in -1.

Ví dụ 1:

Input:

8 10
1 3 5 1 2 4 1 9

Output:

2

(Giải thích: A[1...4] = 10 (dài 4). A[2...4] = 10 (dài 3). A[7...8] = 1+9 = 10 (dài 2). A[8...8] = 9 (< 10). Đoạn ngắn nhất có tổng >= 10 là [1, 9] (dài 2).)