Bài tập

Cho một dãy số nguyên \(A\) gồm \(n\) phần tử.

Với mỗi đoạn con \(A[l..r]\) (\(1 \le l \le r \le n\)), ta định nghĩa:

• \(W(l,r,x)\) là số lần giá trị \(x\) xuất hiện trong đoạn \(A[l],A[l+1],\dots,A[r]\).

• Gọi \(B\) là dãy gồm các phần tử đoạn \(A[l..r]\), và sắp xếp \(B\) tăng dần được dãy \(C\).

  Tập trung vị của đoạn là:
  $
  S(l,r) = { C[\lfloor (k-1)/2 \rfloor],\; C[\lceil (k-1)/2 \rceil] },
  $
  trong đó \(k = r-l+1\).

Giá trị của đoạn \((l,r)\) được định nghĩa là:
$
\max_{x \in S(l,r)} W(l,r,x).
$

Lưu ý: tập \(S(l,r)\) sẽ chứa phần tử trung vị duy nhất nếu đoạn có số phần tử lẻ, và chứa hai phần tử trung vị nếu đoạn có số phần tử chẵn.

Yêu cầu: Tìm giá trị lớn nhất trong tất cả các đoạn \((l,r)\).

\InputFile

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 5 \times 10^5\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(A_i\) (\(1 \le A_i \le n\)).

\OutputFile

In ra một số nguyên duy nhất --- giá trị lớn nhất có thể đạt được.

\Scoring

• \(11\) điểm: \(n \le 100\).
• \(17\) điểm: \(n \le 2 \times 10^3\).
• \(7\) điểm: tồn tại \(x\) sao cho dãy tăng đến \(x\) rồi giảm sau đó.
• \(12\) điểm: \(A_i \le 3\).
• \(13\) điểm: mỗi giá trị xuất hiện nhiều nhất 2 lần.
• \(22\) điểm: \(n \le 8 \times 10^4\).
• \(18\) điểm: không có ràng buộc thêm.

Example

7
1 2 3 1 2 1 3

3

9
1 1 2 3 4 3 2 1 1

2

Bin là một cậu học sinh rất có duyên với số \(4\), cậu có \(4\) người bạn gái, \(4\) năm học sinh giỏi, \(4\) cái máy tính,..... Bởi vậy từ lâu cậu đã coi số \(4\) là con số may mắn của đời mình.

Hôm nay trên lớp Bin được thầy giáo toán học Nhã giảng bài về ước của các số, vậy nên Bin cũng đã nghĩ về một vấn đề toán học liên quan đến con số \(4\) của mình. Cậu tự hỏi nếu có \(1\) dãy số tự nhiên từ \(l\) đến \(r\) thì trong dãy đó có bao nhiêu số tự nhiên có đúng \(4\) ước nguyên dương.

Bin vì suy nghĩ bài toán này liên tiếp \(4\) ngày \(4\) đêm đến mất ăn mất ngủ mà vẫn chưa xong. Vì vậy các bạn hãy giúp cậu ấy nhé, nếu làm được thì sẽ được Bin tặng một món quà đấy !

Input

• Dòng đầu tiên là số truy vấn \(Q\).

• \(Q\) dòng tiếp theo mỗi dòng là hai số nguyên dương \(l\) và \(r\).

Output

• \(Q\) dòng là kết quả của các truy vấn tương ứng.

Example

1
7 9

1

Scoring

• \(30\%\) test có \(Q ≤ 10\) và \(l,r ≤ 10^5\).

• \(30\%\) test có \(Q ≤ 100\) và \(l,r ≤ 10^7\).

• \(40\%\) test có \(Q ≤ 10^5\) và \(l,r ≤ 10^7\).

An rất yêu thích tuyết. Trong \(n\) ngày, mỗi ngày Bình tạo ra một đống tuyết có thể tích \(v_i\).
Nhưng mỗi ngày, nhiệt độ \(t_i\) khiến mỗi đống tuyết (kể cả đống mới tạo) bị giảm đúng \(t_i\) đơn vị.
Đống tuyết nào giảm xuống \(\le 0\) thì biến mất.

Nhiệm vụ của bạn: Tính tổng thể tích tuyết bị tan chảy trong mỗi ngày.

Input

• Dòng 1: số nguyên \(n\) (\(1 \le n \le 10^5\)).
• Dòng 2: \(v_1, v_2, \dots, v_n\) (\(0 \le v_i \le 10^9\)).
• Dòng 3: \(t_1, t_2, \dots, t_n\) (\(0 \le t_i \le 10^9\)).

Output

Một dòng gồm \(n\) số --- lượng tuyết tan trong từng ngày.

Example

3
10 10 5
5 7 2

5 12 4

Scoring

• Subtask 1 (10%): \(t_i = 0\).
• Subtask 2 (30%): \(n, t_i, v_i \le 10^3\).
• Subtask 3 (60%): Không có ràng buộc thêm.

Vua của vương quốc Algorithmia muốn quy hoạch một khu vườn hình chữ nhật trong khuôn viên hoàng cung. Khu đất dự kiến được chia thành lưới ô vuông kích thước \(n \times m\). Mỗi ô \((i, j)\) có độ phì nhiêu của đất là \(a_{i,j}\).

Nhà vua muốn rào một khu đất hình chữ nhật con (có các cạnh song song với các cạnh của khu đất lớn) để trồng một loài hoa quý. Loài hoa này rất kén chọn, nó chỉ phát triển tốt nếu tổng độ phì nhiêu của toàn bộ khu đất hình chữ nhật đó nằm trong khoảng từ \(L\) đến \(R\).

Nhiệm vụ của bạn là đếm xem có bao nhiêu cách chọn một hình chữ nhật con thỏa mãn yêu cầu của nhà vua.

Input

Vào từ tệp văn bản KHUVUON.INP có cấu trúc:

• Dòng đầu tiên chứa bốn số nguyên \(n, m, L, R\) (\(1 \le n, m \le 500, 1 \le L \le R \le 10^{12}\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số nguyên dương biểu diễn ma trận độ phì nhiêu \(a\) (\(1 \le a_{i,j} \le 10^9\)).

Output

Ghi ra tệp văn bản KHUVUON.OUT một số nguyên duy nhất là số lượng hình chữ nhật con thỏa mãn.

Example

3 3 3 5
1 1 1
1 1 1
1 1 1

10

Scoring

• Subtask 1 (\(30\%\) số điểm): \(n, m \le 10\).
• Subtask 2 (\(30\%\) số điểm): \(n, m \le 100\).
• Subtask 3 (\(40\%\) số điểm): Không có ràng buộc gì thêm.