Cho một dãy A gồm N số nguyên a1, a2, a3, ..., aN đã được sắp xếp tăng dần. Bạn cần trả lời Q truy vấn sau:

Cho 3 số l, r, x, có bao nhiêu số có giá trị x trong dãy con al, a(l+1), a(l+2), ..., ar?

Đầu vào:

Dòng đầu tiên gồm duy nhất số nguyên N (N <= 10^6) - kích thước mảng.

Dòng thứ hai gồm N số nguyên ai (0 <= ai <= 10^9).

Dòng thứ ba gồm số truy vấn Q (Q <= 10^5) - số truy vấn.

Q dòng tiếp theo mỗi dòng gồm 3 số l,r,x (0 <= l <= r <= n-1).

Đầu ra:

Q dòng cho biết có bao nhiêu số có giá trị x trong dãy con al, a(l+1), a(l+2), ..., ar? ở mỗi truy vấn.

Input:

7
1 2 3 3 4 4 5
2
0 6 5
0 5 4

Output:

1
2

Trong một liên hoan phim, n bộ phim sẽ được chiếu. Bạn biết thời gian bắt dầu và kết thúc của mỗi bộ phim. Số lượng phim tối đa bạn có thế xem toàn bộ là bao nhiều? Biết rằng nếu thời gian kết thúc của bộ phim trước bằng hoặc nhỏ hơn thời gian bắt đầu của bộ phim sau thì bạn có thể xem cả 2 phim này.

Định dạng đầu vào: Dòng nhập đầu tiên có số nguyên n là số lượng phim. Sau đó, có n dòng mô tả các bộ phim. Mỗi dòng có hai số nguyên a và b là thời gian bắt đầu và kết thúc của một bộ phim.

Ràng buộc: 1 < n, m <= 2.10^5; 1 ≤ a, b ≤ 10^9

Định dạng đầu ra: In một số nguyên là số lượng phim tối đa.

Input:

3
3 5
4 6
2 4

Output:

2

Cho dãy số A gồm N phần tử được đánh số từ 0 đến N-1. Hãy tìm chỉ số i đầu tiên sao cho A[i] == i. Nếu không có, in -1.

Dữ liệu vào:

Dòng 1: Số nguyên dương N.

Dòng 2: N số nguyên A0, A1, ..., AN-1.

Dữ liệu ra: Chỉ số i tìm được hoặc -1.

Ràng buộc: 1 <= N <= 10^6; |Ai| <= 10^9.

Mảng không nhất thiết phải sắp xếp.

Ví dụ 1:

Input:

5 
-1 0 2 5 10

Output:

2

Ví dụ 2:

Input:

3 
1 2 3

Output:

-1

Cho một chuỗi ký tự S và một ký tự C. Hãy tìm vị trí đầu tiên (tính từ 0) của C trong S.

Dữ liệu vào:

Dòng 1: Chuỗi S (không chứa dấu cách).

Dòng 2: Ký tự C.

Dữ liệu ra: Chỉ số đầu tiên của C hoặc -1.

Ràng buộc: Độ dài S <= 10^6.

Ví dụ 1:

Input:

programming 
r

Output:

1

Ví dụ 2:

Input:

hello 
z

Output:

-1

Cho dãy số A gồm N phần tử. Một phần tử được gọi là cực đại địa phương nếu nó lớn hơn cả phần tử đứng liền trước và liền sau nó (nếu có). Hãy đếm số lượng cực đại địa phương trong dãy.

Dữ liệu vào:

Dòng 1: Số nguyên dương N.

Dòng 2: N số nguyên A1, A2, ..., AN.

Dữ liệu ra: Số lượng cực đại địa phương.

Ràng buộc: 1 <= N <= 10^6; |Ai| <= 10^9.

Ví dụ 1:

Input:

5 
1 5 2 4 3

Output:

2

Ví dụ 2:

Input:

3 
1 1 1

Output:

0

Cho dãy số A gồm N phần tử và một số nguyên X. Hãy tìm khoảng cách lớn nhất giữa chỉ số đầu tiên và chỉ số cuối cùng mà X xuất hiện. Nếu X xuất hiện ít hơn 2 lần hoặc không xuất hiện, in ra 0.

Dữ liệu vào:

Dòng 1: Số nguyên N và X.

Dòng 2: N số nguyên A1, A2, ..., AN.

Dữ liệu ra:

Khoảng cách lớn nhất (LastIndex - FirstIndex).

Ràng buộc: 1 <= N <= 10^6; |Ai|, |X| <= 10^9.

Ví dụ 1:

Input:

6 5 
5 1 2 5 3 5

Output:

5

Ví dụ 2:

Input:

4 10 
1 2 3 4

Output:

0

Cho mảng a gồm n phăn tử và số nguyên dương k. Đếm số lượng cặp số ai, aj (i != j) có tổng nhỏ hơn k.

Định dạng đầu vào: Dòng thứ 1 là số lượng phần tử trong mảng và số nguyên dương k; Dòng thứ 2 là n phần tử trong mảng

Ràng buộc: 2<=п<=10^6; 1<=k<=10^6; 0<=a(i)<=10^6;

Định dạng đầu ra: In ra số lượng cặp số có tổng bằng k

Input:

4 5
2 2 2 2

Output:

6

Cho dãy số thực A gồm N phần tử và một số thực X. Hãy tìm phần tử trong mảng có giá trị gần với X nhất (trị tuyệt đối của hiệu số là nhỏ nhất). Nếu có nhiều số, in ra số xuất hiện đầu tiên.

Dữ liệu vào:

Dòng 1: Số nguyên N và số thực X.

Dòng 2: N số thực A1, A2, ..., AN.

Dữ liệu ra: Giá trị của phần tử gần X nhất. Làm tròn không lấy chữ số nào sau phần thập phân.

Ràng buộc: 1 <= N <= 10^6; -10^9 <= Ai, X <= 10^9.

Ví dụ 1:

Input:

5 3.5 
1.0 2.0 5.0 4.0 3.0

Output:

4

Ví dụ 2:

Input:

4 10.0 
1.0 20.0 15.0 5.0

Output:

15

Cho một mảng A gồm N số nguyên chưa được sắp xếp. Có Q truy vấn được đưa ra, mỗi truy vấn yêu cầu bạn kiểm tra một số nguyên X và đếm xem X xuất hiện bao nhiêu lần trong mảng A.

Gợi ý: Vì số lượng truy vấn Q rất lớn, việc dùng vòng lặp quét toàn bộ mảng cho mỗi câu hỏi sẽ bị quá thời gian. Các em cần sắp xếp mảng trước, sau đó vận dụng Tìm kiếm nhị phân (hoặc các hàm lowerbound, upperbound trong C++) để tối ưu hóa thời gian tìm kiếm.

Đầu vào:

• Dòng thứ nhất chứa hai số nguyên dương N và Q lần lượt là số lượng phần tử của mảng và số lượng truy vấn.

• Dòng thứ hai chứa N số nguyên A[i] cách nhau bởi khoảng trắng.

• Q dòng tiếp theo, mỗi dòng chứa một số nguyên X tương ứng với một truy vấn.

Ràng buộc:

• 1 <= N, Q <= 10^5

• -10^9 <= A[i], X <= 10^9

Đầu ra:

In ra Q dòng, mỗi dòng là số lần xuất hiện của X tương ứng với từng truy vấn.

Ví dụ:

Input 01:

5 3
5 1 4 6 3
3
6
10

Output 01:

1
1
0

Input 02:

6 4
1 3 1 4 1 7
1
2
4
7

Output 02:

3
0
1
1