[2025.05.09] - CPPA1250301 - Kiểm tra giữa khóa

Bạn nhận được tất cả các số từ \(1\) đến \(n\) trừ một số. Nhiệm vụ của bạn là tìm số bị thiếu đó.

Input

• Dòng đầu tiên chứa một số nguyên \(n\).
• Dòng thứ hai chứa \(n-1\) số. Các số khác nhau đôi một và mỗi số có giá trị từ \(1\) đến \(n\).

Output

• In ra số còn thiếu.

Constraints

• \(2 \le n \le 2 \cdot 10^5\)

Example

Sample input

5
2 3 1 5

Sample output

4

Cho một số nguyên dương \(n\) và một mảng \(A\) chứa \(n\) số nguyên (có thể âm). Bạn muốn cắt một nhát cắt trên mảng đó để chia mảng đó thành hai đoạn trái và phải, sao cho cả hai đoạn đều có ít nhất một phần tử và tổng các phần tử của hai đoạn bằng nhau.

Đề bài yêu cầu đếm có bao nhiêu cách cắt thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) \((1 \leq n \leq 2*10^5)\)
• Dòng thứ hai chứa \(n\) số nguyên \(A_i,\) là số thứ \(i\) của mảng \(A (|A_i| \leq 10^9)\)

Output

• Số cách cắt mảng \(A\) cho trước, sao cho tổng của phân đoạn trái và phân đoạn phải sau khi cắt có tổng các phần tử bằng nhau.

Example

4
1 2 2 1

1

6
1 1 1 3 -3 3

2

Gần đến tết Tân Sửu 2021, \(n\) bạn học sinh lớp A5 khóa 16-19 đang họp lớp và quyết định rằng Chủ nhật tuần này sẽ đi chơi công viên Châu Phi.

Ở trò chơi "Tàu lượn siêu tốc", mỗi hàng của tàu sẽ chứa tối đa hai chỗ ngồi, và tổng cân nặng hai chỗ ngồi này có giá trị không quá \(x\).

Vậy khi đến chơi tàu lượn siêu tốc, tàu lượn trên phải có ít nhất bao nhiêu hàng ngồi để tất cả các bạn A5 có thể lên chơi 1 lúc.

Input

• \(n, x(1 \leq n\leq 2*10^5, 1 \leq x \leq 10^9)\).
• \(n\) số nguyên, \(1 \leq a_i \leq x\) cân nặng của bạn thứ i .

Output

• số hàng ngồi

Example

4 10
7 2 3 9 

3