Kiểu mảng 1 chiều

Sau kì nghỉ Tết, thầy Hải trở lại trường lớp dạy thuật toán và cấu trúc dữ liệu. Năm nay thầy Hải chào đón học sinh bằng một bài tập về mảng cơ bản.

Thầy Hải cho bạn 2 mảng \(A\) và \(B\) (mỗi mảng đều có \(n\) phần tử) và yêu cầu bạn in ra một mảng mới \(C\) gồm \(n\) phần tử trong đó phần tử thứ \(i\) có giá trị: \(C[i] = A[i] + B[i] ( 1 \le i \le n )\).

Input

• Dòng đầu tiên là số \(n\)
• Dòng thứ 2 gồm \(n\) phần tử của mảng A
• Dòng thứ 3 gồm \(n\) phần tử của mảng B

Output

• Gồm 1 dòng là \(n\) phần tử của mảng C

Giới hạn

• \(1 \le n \le 100000\)
• \(1 \le A[i] \le 100000\)
• \(1 \le B[i] \le 100000\)

Example

5
1 2 3 4 5
4 5 3 2 10 

5 7 6 6 15

Cho một dãy gồm n số nguyên dương \(A_1, A_2,…, A_n\). (\(N \le 10^5, A_i \le 10^9\)).

Hãy in số lớn nhất cùng chỉ số của nó, nếu có nhiều số lớn nhất thì in ra chỉ số của số đầu tiên gặp.

Input

• Dòng đầu chứa số \(n\), dòng thứ hai chứa \(n\) số nguyên dương \(A_1, A_2,…, A_n\).

Output

• Dòng đầu chứa số có giá trị lớn nhất, dòng thứ hai chỉ số của nó.

Example

6
91 451 43 3 451 54

451
2

Cho một dãy gồm n số nguyên dương \(A_1, A_2,…, A_n\). (\(N \le 10^5, Ai \le 10^9\)).

Hãy in số nhỏ nhất cùng chỉ số của nó, nếu có nhiều số nhỏ nhất thì in ra các chỉ số của nó.

Input

• Dòng đầu chứa số \(n\), dòng thứ hai chứa \(n\) số nguyên dương \(A_1, A_2,…, A_n\).

Output

• Dòng đầu chứa số có giá trị nhỏ nhất, dòng thứ hai chỉ số của nó.

Example

6
91 32 43 32 451 54

32
2 4

Cho một dãy gồm \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) và số nguyên dương \(k\).

Hãy in số nhỏ nhất lớn hơn \(k\) cùng chỉ số của nó, nếu có nhiều số nhỏ nhất lớn hơn \(k\) thì in ra các chỉ số của nó.

Input

• Dòng đầu chứa số \(n\) và \(k\) \((1 \leq n \leq 10^{5}, 1 \leq k \leq 10^{9})\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq_{i} \leq 10^{9})\).

Output

• Dòng đầu chứa số có giá trị nhỏ nhất lớn hơn \(k\), dòng thứ hai chứa các chỉ số của nó.

Example

6 35
91 32 43 43 451 54

43
3 4

Cho một dãy gồm \(n\) số nguyên dương \(A_1,A_2,…,A_n\). (\(N\leq 10^5\),\(A_i\leq 10^9\)) và số \(x\).

Yêu cầu: Hãy đếm số lần xuất hiện của giá trị \(x\) trong mảng \(A\).

Input

• Dòng đầu chứa số \(n\) và \(x\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(A_1,A_2,…,A_n\).

Output

• Số lần xuất hiện số \(x\) trong mảng \(A\).

Example

6 451
91 451 43 3 451 54

2

Cho dãy số nguyên \(a\) gồm \(n\) phần tử được sắp xếp tăng dần. Hãy xác định giá trị \(x\) có xuất hiện trong mảng hay không ?

Input

• Dòng đâu tiên chứa số hai số nguyên dương \(n\) và \(k\) - độ dài của dãy, số câu hỏi. \((n, k \leq 100000)\)
• \(n\) số, các phần tử dãy \(a\) \((-10^9 \le a_i \le 10^9)\)
• \(k\) số nguyên dương \(x\) \((-10^9 \le x \le 10^9)\).

Output

• Gồm \(k\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

10 10
1 61 126 217 2876 6127 39162 98126 712687 1000000000
100 6127 1 61 200 -10000 1 217 10000 1000000000 

NO
YES
YES
YES
NO
NO
YES
YES
NO
YES

Cho dãy số nguyên \(a\) gồm \(n\) phần tử được sắp xếp tăng dần. Hãy xác định giá trị lớn nhất của \(i\) sao cho \(a_i \le x\). Nếu không có vị trí thõa mãn in ra \(0\).

Input

• Dòng đâu tiên chứa số hai số nguyên dương \(n\) và \(k\) - độ dài của dãy, số câu hỏi. \((n, k \leq 100000)\)
• \(n\) số, các phần tử dãy \(a\) \((-10^9 \le a_i \le 10^9)\)
• \(k\) số nguyên dương \(x\) \((-10^9 \le x \le 10^9)\).

Output

• Gồm \(k\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

 5 5
 3 3 5 8 9
 2 4 8 1 10

0
2
4
0
5

Cho dãy số nguyên \(a\) gồm \(n\) phần tử được sắp xếp tăng dần. Hãy xác định giá trị nhỏ nhất của \(i\) sao cho \(a_i \ge x\). Nếu không có vị trí thỏa mãn in ra \(n + 1\).

Input

• Dòng đâu tiên chứa số hai số nguyên dương \(n\) và \(k\) - độ dài của dãy, số câu hỏi. \((n, k \leq 100000)\)
• \(n\) số, các phần tử dãy \(a\) \((-10^9 \le a_i \le 10^9)\)
• \(k\) số nguyên dương \(x\) \((-10^9 \le x \le 10^9)\).

Output

• Gồm \(k\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

 5 5
 3 3 5 8 9
 2 4 8 1 10

1
3
4
1
6

Nhập vào một dãy \(N\) số nguyên \(A_{1},A_{2},...,A_{N}\).

Hãy in ra màn hình chỉ số phần tử âm đầu tiên và cuối cùng.

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• \(N\) dòng tiếp theo chứa \(N\) số nguyên \(A_{1},A_{2},...,A_{N}\).

Output

• In ra chỉ số phần tử âm đầu tiên và cuối cùng, nếu ko có phần tử dương nào thì in ra \(2\) số \(−1 −1\).

Constraints

• \(1 \leq n \leq 10000\)
• \(|A_{i}| \leq 10^{9}\)

Example

7
7 -6 -4 19 -22 51 -82 

2 7

Cho một dãy gồm \(n\) số nguyên dương \(A_1, A_2,…, A_n\). (\(N ≤ 10^4, A_i ≤ 10^9\)). Hãy in ra dãy số sau khi sắp xếp dãy số giảm dần (\(A_i ≥ A_{i+1}\)).

Input

• Dòng đầu chứa số \(n\),
• Dòng thứ hai chứa \(n\) số nguyên dương \(A_1, A_2,…, A_n\).

Output

• Một dòng chứa dãy số đã sắp xếp giảm dần.

Example

6
91 451 43 3 451 54 

451 451 91 54 43 3

Cho một dãy gồm \(N\) số nguyên dương \(A_1, A_2,…, A_N\).(\(N ≤ 10^4, A_i ≤ 10^9\)) và số \(K\) (\(K ≤ N\)). Hãy in ra số nhỏ thứ \(K\) trong dãy.

Input

• Dòng đầu chứa số \(N, K\),
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2,…, A_N\).

Output

• Một dòng chứa dãy số nhỏ thứ \(K\) trong dãy.

Example

6 4    
91 451 43 3 452 54 

91

Cho một dãy gồm \(N\) số nguyên dương \(A_1, A_2,…, A_N\).(\(N ≤ 10^4, A_i ≤ 10^9\)) và số \(K\) (\(K ≤ N\)). Hãy in ra số lớn thứ \(K\) trong dãy.

Input

• Dòng đầu chứa số \(N, K\),
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2,…, A_N\).

Output

• Một dòng chứa dãy số lớn thứ \(K\) trong dãy.

Example

6 2    
91 451 43 3 452 54 

451

Cho số nguyên dương \(N\) và mảng \(A\) đã được sắp xếp tăng dần. Cho số nguyên \(X\). Hãy đếm số lần \(X\) xuất hiện trong mảng \(A\).

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)).
• Dòng đầu mỗi bộ test nhập vào số nguyên \(N\) và \(X\) (\(1 \leq N \leq 10^3, 1 \leq X \leq 5000\)).
• Dòng thứ hai mỗi bộ test nhập \(N\) số nguyên \(A_i\) (\(1 \leq i \leq N, 1 \leq A_i \leq 5000\)).

Output

• In ra kết quả theo yêu cầu đề bài.

Example

2
5 3
1 2 3 3 3
5 4
1 2 3 5 6

3
0

Cho số nguyên dương \(N\), \(X\) và mảng \(A\) gồm \(N\) số nguyên. Hãy kiểm tra xem \(X\) có xuất hiện trong mảng \(A\) hay không? Nếu có thì in ra 1, còn ngược lại thì in ra 0.

Input

• Nhập số nguyên dương \(N\) và \(X\) (\(1 \leq N \leq 10^5, 1 \leq X \leq 5000\)).
• Nhập \(N\) số nguyên \(A_i\) (\(1 \leq i \leq N, 1 \leq A_i \leq 5000\)).

Output

• In ra kết quả theo yêu cầu đề bài.

Example

5 3
1 2 3 4 5

1

Cho số nguyên dương \(N\) và mảng \(A\) đã được sắp xếp tăng dần. Cho số nguyên \(X\). Hãy tìm vị trí đầu tiên \(X\) xuất hiện trong mảng \(A\), nếu không tồn tại thì in ra -1.

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)):
  • Dòng đầu mỗi bộ test nhập vào số nguyên \(N\) và \(X\) (\(1 \leq N \leq 10^3, 1 \leq X \leq 5000\)).
  • Dòng thứ hai mỗi bộ test nhập \(N\) số nguyên \(A_i\) (\(1 \leq i \leq N, 1 \leq A_i \leq 5000\)).

Output

• In ra kết quả theo yêu cầu đề bài.

Example

2
5 3
1 2 3 3 3
5 4
1 2 3 5 6

3
-1

Cho số nguyên dương \(N\) và mảng \(A\) đã được sắp xếp tăng dần. Cho số nguyên \(X\). Hãy tìm vị trí cuối cùng \(X\) xuất hiện trong mảng \(A\), nếu không tồn tại thì in ra -1.

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)).
  • Dòng đầu mỗi bộ test nhập vào số nguyên \(N\) và \(X\) (\(1 \leq N \leq 10^3, 1 \leq X \leq 5000\)).
  • Dòng thứ hai mỗi bộ test nhập \(N\) số nguyên \(A_i\) (\(1 \leq i \leq N, 1 \leq A_i \leq 5000\)).

Output

• In ra kết quả theo yêu cầu đề bài.

Example

2
5 3
1 2 3 3 3
5 4
1 2 3 5 6

5
-1

Trên một con đường mới mở đã xuất hiện lác đác \(n\) căn nhà vừa xây xong. Người ta đánh địa chỉ các căn nhà bởi dãy \(a_{1}, a_{2}, a_{3}, ... , a_{n}\) bằng cách tính khoảng cách từ vị trí của căn nhà đến đầu đường theo đơn vị mét. Biết địa chỉ các căn nhà, hãy tìm khoảng cách giữa hai nhà gần nhau nhất.

Input

• Dòng thứ nhất là số nguyên \(n\) biểu thị số lượng các căn nhà \((2 \leq n \leq 10^{5})\)
• Dòng thứ hai gồm \(n\) số nguyên \(a_{1}, a_{2}, a_{3}, ... , a_{n}\), mỗi số cách nhau một khoảng trắng là địa chỉ của \(n\) căn nhà. \((0 \leq a_{i} \leq 10^{9})\). Dữ liệu cho đảm bảo không có \(2\) địa chỉ nào trùng nhau.

Output

• Gồm \(1\) dòng duy nhất là số nguyên duy nhất cho biết khoảng cách giữa hai căn nhà gần nhau nhất.

Example

3
1 6 3

2

3
9 3 6

3

Cho mảng \(a\) gồm \(n\) số nguyên dương. Gọi \(L, R\) là \(min\) và \(max\) các phần tử của \(a\). Nhiệm vụ của bạn là tìm số phần tử cần thiết cần thêm vào mảng để mảng có đầy đủ các số trong khoảng [\(L, R\)]. Ví dụ \(a\) = {\(5, 7, 9, 3, 6, 2\)} ta nhận được kết quả là \(2\) tương ứng với các số còn thiếu là \(4, 8\).

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(t\) \((1 \le t \le 100)\).

• Những dòng kế tiếp đưa vào \(t\) bộ test. Mỗi bộ test gồm hai dòng:

  • Dòng đầu tiên đưa vào \(n\) \((1 \le n \le 10^6)\).
  • Dòng tiếp theo là \(n\) số; các số được viết cách nhau một vài khoảng trống \((1 \le a_i \le 10^6)\).

Output

• Đưa ra kết quả mỗi test theo từng dòng.

Example

2
5
4 5 3 8 6
3
2 1 3

1
0

Cho một mảng gồm \(n\) số nguyên dương \(a_{1}, a_{2}, a_{3},..., a_{n}\). Hỏi có bao nhiêu cặp số \(i < j\) và \(a_{i} = a_{j}\).

Lưu ý: Số lượng này có thể rất lớn nên sử dụng kiểu long long.

Input

• Dòng thứ nhất là chiều dài \(n\) của mảng \((1 \leq n \leq 10^{5})\)
• Dòng thứ hai gồm \(n\) số nguyên \(a_{1}, a_{2}, a_{3},..., a_{n}\) \((1 \leq a_{i} \leq 10^{5})\), mỗi số cách nhau một khoảng trắng.

Output

• Gồm 1 dòng duy nhất là số nguyên xác định số lượng các cặp bằng nhau.

Example

5
8 2 9 8 1  

1

7
6 2 4 2 4 3 4

4

Trong lớp học có \(n\) bạn nam và \(m\) bạn nữ. Các bạn nam có chiều cao là \(a_{1}, a_{2},..., a_{n}\). Các bạn nữ có chiều cao là \(b_{1}, b_{2},..., b_{m}\). Nhân dịp lễ tổng kết cuối năm, cả lớp dự định tổ chức buổi khiêu vũ nhưng có điều kiện là trong một đôi khiêu vũ bất kỳ, bạn nam phải cao hơn bạn nữ. Và mỗi bạn không tham gia quá một đôi khiêu vũ. Hãy tính số lượng cặp đôi nhiều nhất thỏa mãn yêu cầu trên.

Input

• Dòng thứ nhất là hai số \(n, m\) mỗi số cách nhau một khoảng trắng \((1 \leq n, m \leq 10^{5})\).
• Dòng thứ hai gồm n số nguyên \(a_{1}, a_{2},..., a_{n}\) là chiều cao các bạn nam \((1 \leq a_{i} \leq 10^{9})\).
• Dòng thứ ba gồm m số nguyên \(b_{1}, b_{2},..., b_{m}\) là chiều cao các bạn nữ \((1 \leq b_{i} \leq 10^{9})\).

Output

• Gồm 1 dòng duy nhất là số lượng đôi khiêu vũ nhiều nhất tính được.

Example

3 2
3 2 1
2 3

1

3 3
4 3 4
2 2 1

3