Cho số nguyên N. Hãy đếm số lượng cặp (i, j) sao cho 1 <= i < j <= N và GCD(i, j) = 1.

Dữ liệu vào:

Dòng 1: N (1 <= N <= 10^6).

Dữ liệu ra:

Số lượng cặp.

Ví dụ:

Input:

4

Output:

5

Các cặp đúng là (1,2), (1,3), (1,4), (2,3), (3,4).

Sau 7769 giờ lặn lội tìm kiếm The Hidden Gems, Tý đặt chân đến một hòn đảo hoang, nơi được đánh dấu là có kho báu. Tuy nhiên, để tới được chỗ kho báu được chôn thì không hề dễ dàng. Cụ thể, để bảo vệ The Hidden Gems, hòn đảo được Tèo giấu tên sắp xếp những tảng đá hình hộp chữ nhật một cách cực kỳ khó hiểu và ngẫu hứng nhằm ngăn cản bước tiến của Tý trong thử thách cuối cùng này. Nhưng với Tý thì dăm ba cái khoản leo trèo vốn là nghề của Tý, do đó Tý dương tự đắc, dự định nghỉ lại một đêm, rồi tối hôm sau sẽ xuất phát. Nhưng người tính không bằng trời tính, trời đổ mưa dữ dội, khiến cho vùng trũng của những tảng đá kia nay đã ngập nước. Với bản lĩnh của một hải tặc vô địch thiên hạ, đầu đội trời, chân đạp đất, Tý không biết bơi nên quyết định nhờ bạn tính toán lượng nước tối đa mà Tý sẽ gặp phải để Tý uống vừa đủ, không vượt quá 2 lít nước mỗi ngày trước khi tiếp cận được The Hidden Gems.

Cụ thể yêu cầu của Tý như sau: Có N hòn đá tảng với chiều cao h, trong đó h là một số không âm được đo đạc trước, với những nơi không có tảng đá nào, thì h = 0. Dựa trên những dữ kiện đó, bạn sẽ cần tính toán lượng mưa lớn nhất mà Tý sẽ gặp phải khi đi từ tảng đá đầu tiên đến tảng đá thứ N, biết sau tảng đá thứ N và trước tảng đá đầu tiên thì hoàn toàn là đất liền. Nơi có nước sẽ là vùng trũng nơi bị ngăn cách bởi các tảng đá ở hai bên (như hình minh họa bên dưới).

Input:

• Dòng đầu tiên chứa một số nguyên N duy nhất (0 < n ≤ 2 * 10^4)

• Dòng thứ hai bao gồm một mảng gồm N số nguyên không âm là chiều cao h của các tảng đá hình hộp chữ nhật (h ≤ 10^5)

Output: Một dòng duy nhất cho biết lượng nước lớn nhất có thể đọng lại trong các vùng trũng của các tảng đá.

Giới hạn: 0 < N ≤ 2 * 10^4; 0 < h ≤ 10^5

Testcase: Như hình minh họa.

Input 01:

12
0 1 0 2 1 0 1 3 2 1 2 1

Output 01:

6

Input 02:

6
4 2 0 3 2 5

Output 02:

9

Tí có N thanh gỗ với độ dài khác nhau. Tí muốn ghép các thanh gỗ này thành các hình chữ nhật. Mỗi hình chữ nhật cần 2 cặp cạnh bằng nhau (ví dụ 2 thanh dài L và 2 thanh dài W). Tí muốn chọn ra 4 thanh gỗ để ghép thành 1 hình chữ nhật sao cho diện tích của nó là lớn nhất có thể. Nếu không thể ghép được, in ra 0.

Dữ liệu vào:

Dòng đầu chứa số nguyên N.

Dòng thứ hai chứa N số nguyên A[i].

Dữ liệu ra:

Diện tích hình chữ nhật lớn nhất.

Giới hạn:

4 <= N <= 10^5

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

Ví dụ 1:

Input:

8 
2 5 2 5 5 2 2 10

Output:

10

Giải thích: Có 4 thanh 2 và 3 thanh 5. Ta có thể ghép hình chữ nhật 2x5. Diện tích 10. Thanh 10 ko có cặp nên bỏ.

Ví dụ 2:

Input:

5 
1 2 3 4 5

Output:

0

Cho mảng A gồm N phần tử đã được sắp xếp tăng dần. Xét tất cả các cặp (i, j) với i < j. Khoảng cách của cặp là A[j] - A[i]. Hãy tìm khoảng cách nhỏ thứ K trong tất cả các cặp.

Dữ liệu vào:

Dòng 1: Hai số nguyên N và K (1 <= N <= 10^5, 1 <= K <= N*(N-1)/2).

Dòng 2: N số nguyên A[i] (0 <= A[i] <= 10^9).

Dữ liệu ra:

Khoảng cách nhỏ thứ K.

Ví dụ:

Input:

4 3 
1 5 10 20

Output:

9

Giải thích: Các khoảng cách: 4, 5, 9, 10, 15, 19. Số nhỏ thứ 3 là 9.

Trong một mảng A gồm N số, một cặp chỉ số (i, j) được gọi là một "nghịch thế" (inversion) nếu i < j nhưng Ai > Aj. Số lượng nghịch thế là một chỉ số quan trọng để đánh giá mức độ "hỗn loạn" của mảng. Dữ liệu mảng rất lớn (N = 10^5), bạn hãy thiết kế cấu trúc dữ liệu hoặc thuật toán đếm (như Merge Sort hoặc Binary Indexed Tree) để tìm ra tổng số nghịch thế trong thời gian O(N log N).

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^9).

Output: Tổng số lượng nghịch thế.

Ví dụ:

Input:

5
2 4 1 3 5

Output:

3

(Giải thích: Các cặp nghịch thế là (2, 1), (4, 1), (4, 3)).