Cho dãy số A[] gồm có N phần tử. Ở mỗi thao tác bạn có thể tăng các phần tử trong mảng lên 1 vài đơn vị, hãy xác định số đơn vị tối thiểu cần thêm vào các phần tử trong mảng sao cho mảng trở thành một dãy tăng chặt. Ví dụ dãy 1 2 3 7 8 là một dãy tăng chặt, nhưng dãy 1 2 2 7 8 không phải là một dãy tăng chặt.

Định dạng đầu vào: Dòng đầu tiên là số nguyên N. Dòng tiếp theo gồm N số nguyên A[i]

Ràng buộc: 1≤ N ≤ 10^6; 0 ≤ A[i] ≤ 10^6

Định dạng đầu ra: In ra số đơn vị tối thiểu cần thêm vào các phần tử trong mảng để dãy tăng chặt.

Input:

5
3 2 7 8 1

Output:

10

Cho mảng A gồm N phần tử, hãy tìm 2 chỉ số i, j khác nhau sao cho 0 <= i < j < N và trị tuyệt đối của tổng của 2 phần tử A[i] và A[j] đạt giá trị lớn nhất.

Định dạng đầu vào: Dòng đầu tiên là số nguyên N. Dòng tiếp theo gồm N số nguyên A[i]

Ràng buộc:

2<=N<=10^6;

-10^9<=A[i]<=10^9

Định dạng đầu ra: In ra đáp án của bài toán là chỉ số i và j thoả mãn

Input 01:

5
-1 -2 -3 10 -5

Output 01:

3 0

Input 02:

5
-1 -2 -3 8 -5

Output 02:

4 2

Cho mảng A có N phần tử và số nguyên dương K, hãy tìm dãy con liên tiếp dài nhất có tổng các phần tử bằng 0. Nếu có nhiều dãy con thỏa mãn thì in ra dãy con đầu tiên, in ra "NOT FOUND" nếu không có dãy con nào có tổng bằng 0

Ràng buộc: ~1 \leq N \leq 10^6~; ~-10^6 \leq abs(A[i]) \leq 10^6~

Input 01:

15
-4 1 2 -1 2 -3 -8 2 1 -2 -8 7 -5 2 8

Output 01:

-4 1 2 -1 2

Input 02:

4
1 2 3 -4

Output 02:

NOT FOUND

Cho mảng A[] gồm N số nguyên không âm và số K. Nhiệm vụ của bạn là hãy chia mảng A[] thành hai mảng con có kích cỡ K và N-K sao cho hiệu giữa tổng hai mảng con là lớn nhất. Ví dụ với mảng A[] = {8, 4, 5, 2, 10}, K = 2 ta có kết quả là 17 vì mảng A[] được chia thành hai mảng (4, 2) và (8, 5,10) có hiệu của hai mảng con là 23-6=17 là lớn nhất.

Định dạng đầu vào: Dòng đầu tiên là 2 số N và K. Dòng thứ 2 là N số trong mảng A

Ràng buộc: 1 ≤ K < N ≤ 10^5; 0 ≤ A[i] ≤ 10^7

Định dạng đầu ra: In ra hiệu lớn nhất có thể.

Input:

8 3
1 1 1 1 1 1 1 1

Output:

2

Cho mắng A[] gồm N phần tử và số nguyên dương K nhiệm vụ của bạn là tìm dãy con liên tiếp dài nhất có tổng chia hết cho K.

Định dạng đầu vào: Dòng thứ nhất gồm N, K; Dòng thứ 2 gồm các phần tử trong mảng A[].

Ràng buộc: 1<=K<=N<=10^6; -10^6<=A[i]<=10^6;

Định dạng đầu vào: In ra dãy con dài nhất hoặc in ra -1 nếu không tồn tại dãy con chia hết cho K.

Input:

12 2
-4 1 4 -4 4 4 -3 4 2 -4 2 4

Output:

12

Tất cả các thành phố của Lineland đều nằm trên trục tọa độ Ox. Do đó, mỗi thành phố được liên kết với vị trí xi - tọa độ trên trục Ox. Không có hai thành phố được đặt tại một điểm. Cư dân Lineland thích gửi thư cho nhau. Một người chỉ có thể gửi thư nếu người nhận sống ở một thành phố khác. Chi phí gửi thư chính xác bằng khoảng cách giữa thành phố của người gửi và thành phố của người nhận. Đối với mỗi thành phố, hãy tính hai giá trị mini và maxi, trong đó mini là chi phí tối thiểu để gửi thư từ thành phố thứ i đến một thành phố khác và maxi là chi phí tối đa để gửi thư từ thành phố thứ i đến một số thành phố khác.

Input: Dòng đầu tiên của đầu vào chứa số nguyên n (2<= n ≤ 10^5) - số lượng thành phố trong Lineland. Dòng thứ hai chứa chuỗi n số nguyên khác nhau x1, x2, ..., xn (-10^9<= xi <=10^9), trong đó xi là tọa độ x của thành phố thứ i. Tất cả các xi là khác biệt và theo thứ tự tăng dần.

Output: In n dòng, dòng thứ i phải chứa hai số nguyên mini, maxi, cách nhau bởi một khoảng trắng, trong đó mini là chi phí tối thiểu để gửi thư từ thành phố thứ i và maxi là chi phí tối đa để gửi thư từ thành phố thứ i.

Ví dụ:

Input:

4 
-5 -2 2 7

Ouput:

3 12
3 9
4 7
5 12

Một ngày nọ, ba người bạn thân nhất Petya, Vasya và Tonya quyết định thành lập một nhóm và tham gia các cuộc thi lập trình. Những người tham gia thường được cung cấp một số vấn đề trong các cuộc thi lập trình. Rất lâu trước khi bắt đầu, những người bạn đã quyết định rằng họ sẽ giải một vấn đề nếu ít nhất hai người trong số họ biết cách giải. Nếu không, bạn bè sẽ không viết lời giải cho vấn đề đó. Cuộc thi này cung cấp n vấn đề cho những người tham gia. Đối với mỗi vấn đề chúng ta biết, người bạn nào chắc chắn lời giải. Giúp bạn bè tìm ra số vấn đề mà họ sẽ viết ra giải pháp.

Input: Dòng đầu vào đầu tiên chứa một số nguyên n (1 <=n <=1000) - số lượng vấn đề trong cuộc thi. Sau đó, n dòng chứa ba số nguyên mỗi số nguyên, mỗi số nguyên là 0 hoặc 1. Nếu số đầu tiên trong dòng bằng 1, thì Petya chắc chắn về lời giải của vấn đề, nếu 0 thì không chắc chắn về lời giải. Số thứ hai cho thấy quan điểm của Vasya về giải pháp, số thứ ba cho thấy quan điểm của Tonya. Các số trên các dòng được phân cách bằng dấu cách.

Output: In một số nguyên duy nhất - số lượng vấn đề mà 3 bạn trên sẽ thực hiện trong cuộc thi.

Ví dụ:

Input:

3
1 1 0
1 1 1
1 0 0

Output:

2

Cho một mảng gồm n (3<=n<=10^7) số nguyên đôi một khác nhau, tìm và in ra 3 số lớn nhất trong mảng.

Ví dụ:

Input:

10
99 13 2 4 0 12 24 58 56 14

Output:

99 58 56

Cho một mảng gồm n (3<=n<=10^7) số nguyên đôi một khác nhau, liệt kê các phần tử trong mảng có ít nhất 2 phần tử khác lớn hơn nó.

Ví dụ:

Input

6
1 5 4 3 2 7

Output

1 4 3 2

Cho một mảng gồm n (3<=n<=10^7) số nguyên đôi một khác nhau, tìm và in ra 3 số nhỏ nhất trong mảng.

Ví dụ:

Input:

7
9 11 78 75 14 6 1

Ouput:

9 6 1

Nhiệm vụ của bạn là: với mỗi ~k = 1, 2, ..., n,~ hãy đếm số cách đặt 2 quân mã trên bàn cờ kích thước ~k × k~ sao cho chúng không tấn công nhau.

Dữ liệu vào: Dòng đầu tiên chứa một số nguyên ~n~ — kích thước tối đa của bàn cờ.

Dữ liệu ra: In ra ~n~ số nguyên, mỗi số ứng với số cách đặt 2 quân mã không tấn công nhau trên bàn cờ kích thước từ 1×1 đến ~n×n~.

Ràng buộc:

~1≤n≤10^4~

Ví dụ :

Input:

8

Output:

0  
6  
28  
96  
252  
550  
1056  
1848

Bạn được cho dãy số từ 1 đến ~n~. Hãy kiểm tra xem có thể chia dãy số này thành hai tập hợp có tổng bằng nhau hay không.

Nếu có thể, hãy in ra một ví dụ về cách chia các số đó.

Dữ liệu vào:

Dòng duy nhất chứa số nguyên n.

Dữ liệu ra:

In "YES" nếu có thể chia được. Ngược lại, in "NO".

Nếu chia được:

~-~In ra số phần tử của tập thứ nhất, sau đó in các phần tử trên một dòng.

~-~Tiếp theo in số phần tử của tập thứ hai, rồi in các phần tử trên một dòng.

Lưu ý: In theo thứ tự giảm dần

Ràng buộc: ~1≤n≤10^6~

Ví dụ:

Input:

7

Output:

YES
3
7 6 1 
4
5 4 3 2

Bạn được cho tất cả các số nguyên từ 1 đến ~n~, ngoại trừ một số bị thiếu. Nhiệm vụ của bạn là tìm ra số bị thiếu đó.

Dữ liệu vào:

~-~Dòng đầu tiên chứa một số nguyên ~n~ — số lượng số cần có (bao gồm cả số bị thiếu).

~-~Dòng thứ hai chứa ~n - 1~ số nguyên khác nhau, mỗi số nằm trong đoạn từ 1 đến n.

Dữ liệu ra:

In ra số nguyên duy nhất bị thiếu.

Ràng buộc:

~2 ≤𝑛≤2⋅10^5~

Ví dụ :

Input:

5
2 3 1 5

Output:

4

Cho một mảng gồm ~n~ số nguyên phân biệt. Gọi một phần tử trong mảng là số bị chi phối nếu tồn tại hai số khác nhau trong mảng sao cho tổng của chúng lớn hơn số đó.

Viết chương trình đếm xem trong mảng có bao nhiêu số bị chi phối.

Input:

~-~Dòng đầu chứa số nguyên: ~n~ ~(3 ≤ n ≤ 10^5)~

~-~Dòng thứ hai chứa ~n~ số nguyên phân biệt: ~a₁, a₂, ..., aₙ~ ~(|aᵢ| ≤ 10^9)~

Output: Một số nguyên duy nhất: số lượng số bị chi phối trong mảng.

Ví dụ :

Input:

5
2 5 9 3 7

Output:

5