# Binary Search

## 2NOT3
Ekko là một cậu bé rất kì lạ, con số yêu thích của cậu ấy là số $2$, nhưng Ekko lại vô cùng ghét số $3$. Vì thế Ekko chỉ thấy thiện cảm với những số tự nhiên chia hết cho $2$ nhưng không chia hết cho $3$.

Một hôm Ekko mang theo $q$ câu hỏi đến nhờ thầy giáo của cậu là Snape giải đáp giúp mình. Câu hỏi thứ $i$ là một số nguyên dương $x_i$ và Ekko muốn biết số tự nhiên $V$ nhỏ nhất sao cho từ $0$ đến $V$ có đúng $x_i$ số tự nhiên mà Ekko thấy thiện cảm. Là cánh tay trái đắc lực của thầy Snape, bạn hãy giải đáp những câu hỏi này.

### Input
Dòng đầu tiên chứa số nguyên dương q

Trong q dòng tiếp theo, dòng thứ $i$ là số nguyên dương $x_i$

### Output
In ra trên $q$ dòng kết quả của $q$ câu hỏi

### Constraints
$q \le 10^5$
$x_i \le 10^{17}$

### Example
#### Input
3
2
5
7
#### Output
4
14
20

---

## SAW
Trong rừng có $n$ cái cây đánh số từ $1$ đến $n$, cây thứ $i$ có độ cao là $h_i$ mét.

Gwen là $1$ tên lâm tặc và thường xuyên dùng cái cưa máy do hắn sáng chế ra để đi chặt cây trong rừng. Nguyên lý hoạt động của cái cưa máy là hắn sẽ đặt nó ở $1$ độ cao $X$ mét cố định, và với cái cây ở vị trí $i$, nếu độ cao của nó lớn hơn vị trí đặt cưa, thì cây đó sẽ bị cưa và Gwen nhận được $X – h_i$ mét gỗ.

Có $q$ câu hỏi, ở câu hỏi thứ $i$, Gwen cần biết vị trí đặt cưa cao nhất có thể là bao nhiêu để vẫn nhận được ít nhất $m_i$ mét gỗ.

### Input
Dòng thứ nhất chứa số nguyên dương $n$

Dòng tiếp theo chứa $n$ số nguyên dương $h_1, h_2, ..., h_n$

Dòng tiếp theo chứa số nguyên dương $q$

Trong $q$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên dương $m_i$

### Constraints
$n, q \le 10^5$
$h_i \le 10^9$
$m_i \le h_1 + h_2 + ... + h_n$

### Example
#### Input
4
20 15 10 17
2
7
4
#### Output
15
16

---

## WANNACRY
Snape là một hacker vô cùng tài giỏi. Hắn ta mới tạo ra một loại virus WannaCry có thể đột nhập mọi máy tính dễ dàng để đánh cắp dữ liệu, ngoài ra khả năng lây lan của nó là rất nhanh: bán kính lây lan lên đến $M$. Tuy nhiên chi phí để tạo ra virus WannaCry là vô cùng đắt đỏ vì thế Snape phải tính toán kỹ lưỡng số lượng trước khi phát tán.

Snape đang muốn dùng con virus này tấn công vào một tập đoàn có $n$ máy tính. Các máy tính của tập đoàn này được đặt trên $1$ đường thẳng, máy thứ $i$ đặt ở vị trí $x_i$. Nếu Snape cài virus vào máy tính $i$, con virus này có thể lây sang máy $j$ nếu khoảng cách từ $i$ đến $j$ không vượt quá $M$, tức là $|x_i-x_j| \le M$. Snape muốn nhờ bạn tính toán số lượng virus nhỏ nhất cần dùng để virus có thể lây lan hết cả $n$ máy.

### Input
Dòng đầu tiên chứa $2$ số nguyên dương $n, M$

Dòng tiếp theo chứa $n$ số nguyên $x_1, x_2, ..., x_n$

### Output
In ra trên $1$ dòng số virus nhỏ nhất cần dùng

### Constraints
$n \le 200000, M ≤ 10^{12}$
$|x_i| \le 10^{12}$

### Example
#### Input
4 3
1 12 15 18
#### Output
2

---

## PARTY
Nhân dịp kỉ niệm $10$ năm thành lập công ty SpaceSpeaker, giám đốc âm nhạc Touliver muốn mời $n$ người bạn thân đến tham dự buổi tiệc. Người bạn thứ $i$ $(1 \le i \le n)$ của Touliver có số tài sản là $a_i$ và độ uy tín trong giới truyền thông là $b_i$.

Để buổi tiệc diễn ra trong không khí vui vẻ và không có sự chênh lệch giàu nghèo, Touliver muốn đảm bảo không có bất cứ $2$ người nào tham gia buổi tiệc có **độ chênh lệch tài sản lớn hơn hoặc bằng $D$**. Tất nhiên vị giám đốc âm nhạc cũng muốn tổng độ uy tín của những người tham gia tiệc là lớn nhất có thể. Hãy giúp Touliver tổ chức buổi tiệc theo đúng ý của ông ấy.

### Input
Dòng đầu tiên chứa $2$ số nguyên dương $n, D$

Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa $2$ số nguyên dương $a_i, b_i$

### Output
In ra trên $1$ dòng độ uy tín lớn nhất của buổi tiệc

### Constraints
$n \le 200000, D \le 10^9$
$a_i, b_i \le 10^9$

### Example
#### Input
4 3
10909234 9
10909235 98
10909236 8
10909237 10
#### Output
116

---

## DELPAIR
Cho số nguyên dương $n$ và dãy $n$ số nguyên dương $a_1, a_2, ..., a_n$. Gọi trung bình cộng của $n$ số này là $K$. Hãy đếm số cặp $(i, j)$ $(1 \le i < j < n)$ sao cho sau khi xóa $2$ số $a_i, a_j$ ra khỏi dãy, trung bình cộng của $n-2$ số còn lại vẫn là $K$.

### Input
Dòng đầu tiên chứa số nguyên dương $T$ là số bộ câu hỏi $(T \le 5)$

Các dòng tiếp theo mô tả các bộ câu hỏi, mỗi bộ câu hỏi gồm:

* Dòng đầu tiên chứa số nguyên dương $n$
* Dòng tiếp theo chứa n số nguyên dương $a_1, a_2, ..., a_n$

### Output
In ra trên $T$ dòng kết quả của $T$ bộ test

### Constraints
$n \le 10^6$
$a_i \le 10^9$

### Example
#### Input
2
5
1 2 3 4 5
6
1 3 4 3 2 2
#### Output
2
5

<!-- ## FACTORY
KINGDO là một nhà máy chuyên sản xuất các loại bánh trung thu. Nhà máy có tất cả $N$ máy sản xuất và đóng gói bánh. Kể từ thời điểm khởi động, máy thứ $i$ sẽ mất $t_i$ giây để sản xuất ra chiếc bánh đầu tiên, và sau đó cứ mỗi $c_i$ giây máy này sẽ sản xuất thêm một chiếc bánh.

Những chiếc máy này tuy có thể tự động sản xuất và đóng gói bánh, nhưng không thể tự động cho bánh vào thùng, vì thể nhà máy đã cử $M$ công nhân $(M \le N)$, mỗi công nhân sẽ đảm nhận đứng ở $1$ máy duy nhất để cho những chiếc bánh máy này sản xuất vào thùng. Những máy không có công nhân nào đảm nhận sẽ không được khởi động.

Một doanh nghiệp đã đặt đơn nhà máy $X$ chiếc bánh trung thu. Là chủ của nhà máy sản xuất này, Bob muốn sắp xếp $M$ công nhân này vào một số máy, sau đó khởi động tất cả những máy này cùng lúc, sao cho thời gian để sản xuất ra $X$ chiếc bánh là nhanh nhất có thể.

### Input
Dòng đầu tiên chứa $3$ số nguyên dương $N, M, X$

Dòng tiếp theo chứa $N$ số nguyên dương $t_1, t_2, ..., t_N$

Dòng cuối cùng chứa $N$ số nguyên dương $c_1, c_2, ..., c_N$

### Output
In ra trên $1$ dòng thời gian ngắn nhất để sản xuất ra $X$ chiếc bánh

### Constraints
$M \le N \le 50000$
$X \le 10^9$
$t_i, c_i \le 100$

### Example
#### Input
3 2 5
5 1 2
1 2 1
#### Output
4 -->