Luyện Tập #20

Bạn được cho một danh sách gồm \(n\) số nguyên. Nhiệm vụ của bạn là tính số lượng giá trị phân biệt xuất hiện trong danh sách.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(n\): số lượng phần tử trong danh sách.
• Dòng thứ hai chứa \(n\) số nguyên:

Dữ liệu ra

In ra một số nguyên duy nhất: số lượng giá trị phân biệt xuất hiện trong danh sách.

Ràng buộc

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le x_i \le 10^9\)

Ví dụ

Input

5
2 3 2 2 3

Output

2

Bạn được cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là tìm hai giá trị ở hai vị trí khác nhau sao cho tổng của chúng bằng \(x\).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(x\): kích thước của mảng và tổng cần tìm.

Dòng thứ hai chứa \(n\) số nguyên:

Đây là các phần tử của mảng.

Dữ liệu ra

In ra hai số nguyên là vị trí của hai phần tử có tổng bằng \(x\).

Nếu có nhiều đáp án, bạn có thể in ra một đáp án bất kỳ. Nếu không tồn tại đáp án, in ra:

IMPOSSIBLE

Ràng buộc

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le x, a_i \le 10^9\)

Ví dụ

Input

4 8
2 7 5 1

Output

2 4

Bạn được cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là tìm tổng lớn nhất của một đoạn con liên tiếp và không rỗng trong mảng.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\): số lượng phần tử của mảng.

Dòng thứ hai chứa \(n\) số nguyên:

Đây là các phần tử của mảng.

Dữ liệu ra

In ra một số nguyên duy nhất: tổng lớn nhất của một đoạn con liên tiếp và không rỗng.

Ràng buộc

• \(1 \le n \le 2 \cdot 10^5\)
• \(-10^9 \le x_i \le 10^9\)

Ví dụ

Input

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

Output

9

Có \(n\) trẻ em muốn đi vòng quay khổng lồ. Nhiệm vụ của bạn là sắp xếp cabin cho mỗi trẻ.

Mỗi cabin có thể chứa một hoặc hai trẻ em. Ngoài ra, tổng cân nặng của những trẻ em trong một cabin không được vượt quá \(x\).

Bạn biết cân nặng của từng trẻ em.

Hãy xác định số cabin ít nhất cần sử dụng.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng trẻ em và tổng cân nặng tối đa mà một cabin có thể chứa.

Dòng tiếp theo chứa \(n\) số nguyên:

Trong đó \(p_i\) là cân nặng của trẻ em thứ \(i\).

Dữ liệu ra

In ra một số nguyên duy nhất: số cabin ít nhất cần sử dụng.

Ràng buộc

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le x \le 10^9\)
• \(1 \le p_i \le x\)

Ví dụ

Input

4 10
7 2 3 9

Output

3

Trong một liên hoan phim, có \(n\) bộ phim sẽ được trình chiếu.

Bạn biết thời gian bắt đầu và thời gian kết thúc của mỗi bộ phim.

Hãy xác định số lượng phim lớn nhất mà bạn có thể xem trọn vẹn.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\): số lượng bộ phim.

Trong \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\): thời gian bắt đầu và thời gian kết thúc của một bộ phim.

Dữ liệu ra

In ra một số nguyên duy nhất: số lượng phim lớn nhất có thể xem trọn vẹn.

Ràng buộc

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le a < b \le 10^9\)

Ví dụ

Input

3
3 5
4 9
5 8

Output

2

Bạn được cho \(n\) số nguyên. Với mỗi số nguyên, nhiệm vụ của bạn là xác định số lượng ước số của nó.

Ví dụ, nếu \(x = 18\), đáp án là \(6\) vì các ước số của \(18\) là:

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\): số lượng số nguyên cần xử lý.

Trong \(n\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(x\).

Dữ liệu ra

Với mỗi số nguyên \(x\), in ra số lượng ước số của nó trên một dòng riêng.

Ràng buộc

• \(1 \le n \le 10^5\)
• \(1 \le x \le 10^6\)

Ví dụ

Input

3
16
17
18

Output

5
2
6

Trong số học, số phong phú là các số mà tổng các ước số của số đó, không kể chính nó, lớn hơn số đó.

Ví dụ, số \(12\) có tổng các ước số không kể \(12\) là:

Do đó, \(12\) là một số phong phú.

Bạn hãy lập trình đếm xem có bao nhiêu số phong phú trong đoạn \([L, R]\).

Input

Gồm hai số nguyên \(L\) và \(R\):

Output

In ra một số nguyên duy nhất là số lượng số phong phú trong đoạn \([L, R]\).

Giới hạn

• Có \(50\%\) số test thỏa mãn:

Sample Input

1 50

Sample Output

9

Ghi chú

Từ \(1\) đến \(50\) có \(9\) số phong phú là: