LQDOJ Contest #9

Một số nguyên dương \(N\) là một số đặc biệt khi tổng các ước số của nó (trừ chính nó) lớn hơn \(M\) với \(M\) là một số nguyên dương được cho trước. Ví dụ với \(M = 5\) thì \(N = 6\) là số đặc biệt vì \(1 + 2 + 3 = 6 > 5\). Nhưng với \(M = 6\) hay \(M = 10\) thì \(N = 6\) không phải số đặc biệt.

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vấn có ba số nguyên dương lần lượt là \(L,R,X\). Bạn hãy đếm số đặc biệt có trong đoạn \([L;R]\) tính theo \(X\). Nói cách khác, bạn hãy đếm số thỏa mãn rằng tổng các ước số của nó (trừ chính nó) lớn hơn \(X\) có trong đoạn \([L;R]\).

Input

• Dòng đầu tiên chứa số nguyên dương \(Q\) \((1 \le Q \le 10^5)\).
• \(Q\) dòng tiếp theo mỗi dòng chứa ba số nguyên dương lần lượt là \(L,R,X\) \((1 \le L \le R \le 10^5, 1 \le X \le 10^5)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Có \(Q,R \le 10^3\).

• Subtask \(2\) (\(20\%\) số điểm): Có \(R \le 10^4\) và \(X = 10\).

• Subtask \(3\) (\(30\%\) số điểm): Có \(X \le 10\).

• Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

2
1 10 5
15 20 8

3
4

Có \(N\) người chơi trong một giải đấu, mỗi người được đánh số từ \(1\) tới \(N\). Thay vì đấu nhau theo các hình thức thông thường như đấu vòng tròn, đấu loại trực tiếp, v.v, ban tổ chức lại ra thể lệ đấu như sau: Hai người chơi thứ \(i\), và người chơi thứ \(j\) sẽ có 1 trận đấu với nhau nếu tổng hai số thứ tự của họ là một số lẻ (hay nói cách khác \(i\) \(+\) \(j\) là một số lẻ). Vì ban tổ chức bận nhiều việc khác nên họ quyết định nhờ bạn tính giúp họ đếm số cặp đấu sẽ diễn ra trong giải đấu biết rằng một người chơi không được gặp từng đối thủ của mình quá một lần.

Yêu cầu: Bạn hãy giúp ban tổ chức đếm số cặp đấu có thể diễn ra theo yêu cầu của họ.

Input

• Chứa một số nguyên dương duy nhất \(N\) \((2 \le N \le 10^9)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): Có \(N\le 1000\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

3

2

shiba là một ông chủ của một công ty chuyên đi giao hàng. Anh ấy sống ở một thành phố có đúng \(10^9\) ngôi nhà được xếp thành một hàng. Mỗi nhà có một số, nhà có số \(i\) liền kề với những ngôi nhà có số \(i-1\) và \(i+1\) (nếu có). Công ty của shiba đã nhận được \(N\) đơn giao hàng tại nhà \(H_i\) vào đúng thời điểm \(T_i\) (Không có hai đơn hàng nào ở cùng một thời điểm và ở cùng một nhà).

Để tiết kiệm tiền, shiba muốn biết anh sẽ cần bao nhiêu xe tải giao hàng để có thể hoàn thành tất cả các đơn. Những chiếc xe tải anh ta sẽ mua có thể di chuyển sang nhà bên trái hoặc nhà bên phải mà bên cạnh chiếc xe đang đứng trong vòng một giây (các chiếc xe cũng có thể ở cùng một ngôi nhà). Tại thời điểm ban đầu, xe tải có thể đậu trước bất cứ ngôi nhà nào mà shiba chọn.Ngoài ra, thời gian từ lúc chiếc xe đã đến nhà lúc hàng được giao tận tay của khách là không đáng kể (có thể tính là \(0\)). Tuy nhiên shiba là một người bận rộn và không có thời gian cho những công việc dễ dàng như thế này.

Yêu cầu: Bạn hãy giúp shiba viết một chương trình để tìm số lượng xe tải giao hàng tối thiểu mà anh ấy cần.

Input

• Dòng đầu tiên chứa số nguyên \(N\) – số đơn giao hàng mà công ti shiba có \((1 \le N \le 10^6)\).

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(T_i\) và \(H_i\) lần lượt là thời gian thời điểm để giao đơn hàng cho một ngôi nhà và số nhà của ngôi nhà đó \((1 \le T_i,H_i \le 10^9)\).

• Bộ dữ liệu luôn đảm bảo rằng \(T_i \neq T_j\) hoặc \(H_i \neq H_j\) với mọi \(i \neq j\).

Output

• In ra số nguyên dương duy nhất là số lượng xe tải giao hàng tối thiểu mà shiba cần.

Scoring

• Subtask \(1\) (\(26\%\) số điểm): Có \(N\le{10}^3\).
• Subtask \(2\) (\(26\%\) số điểm): Có \(N\le{10}^4\).
• Subtask \(3\) (\(26\%\) số điểm): Có \(N\le 2 \times {10}^5\).
• Subtask \(4\) (\(22\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
2 3
1 1
5 1
5 4

2

Peter có \(1\) bộ bài gồm \(n\) lá, với các lá được đánh số từ \(1\) đến \(n\), lá thứ \(i\) có mặt trên là giá trị \(a_i\) và mặt dưới là giá trị \(b_i\). Bạn hãy giúp Peter lật hoặc úp các lá bài sao cho số lượng giá trị khác nhau hiện lên ở trên là nhiều nhất có thể biết rằng bạn có thể lật hoặc úp vô số lần.

Input

• Dòng đầu tiên ghi số \(n\) \((1 \le n \le 10^5)\);
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(2\) số \(a_i\) và \(b_i\) \((1 \le a_i, b_i \le n)\)

Output

• Gồm \(1\) số nguyên dương là kết quả bài toán.

Example

4
1 2
1 3
4 2
2 3

4

Ông Từ đang ôn bài tập về dãy số, hôm nay ông có \(1\) dãy số \(a\) gồm \(n\) phần tử, đối với ông \(1\) dãy con liên tiếp của \(a\) được xem là dãy đẹp nếu số lượng phần tử của dãy con đó không bé hơn giá trị bé nhất trong dãy con và không lớn hơn giá trị lớn nhất trong dãy con.
Hay nói cách khác, đoạn con từ \(i\) đến \(j\) được xem là đẹp nếu \(Min(a_i, a_{i + 1},...a_j) \le j - i + 1 \le Max(a_i, a_{i + 1},...a_j)\). Ông Từ muốn tính số cách chia dãy thành các đoạn đẹp sao cho mỗi phần tử phải thuộc duy nhất \(1\) đoạn đẹp. Vì số cách có thể rất lớn nên bạn hãy in số cách dưới dạng modulo cho \(10^9 + 7\) giúp ông nhé.

Input

• Dòng đầu tiên ghi số \(n\) \((1 \le n \le 10^5)\);
• Dòng tiếp theo gồm \(n\) số mô tả mảng \(a\) \((1 \le a_i \le n)\).

Output

• Gồm \(1\) số nguyên là kết quả bài toán.

7
1 6 2 3 4 3 4

6