Có \(n\) drone được đánh số liên tiếp từ \(L\) đến \(L + n - 1\).
Danh sách hiện tại chỉ còn \(n - 1\) số hiệu do một drone bị mất.
Hãy xác định số hiệu của drone bị thiếu.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, L\) (\(1 \le n \le 10^5\), \(1 \le L \le 10^9\)).
• Dòng thứ hai chứa \(n - 1\) số nguyên, là danh sách số hiệu của các drone còn lại.

Output

• In ra một số nguyên duy nhất, là số hiệu của drone bị thiếu.

Examples

5 1
5 1 3 2

4

5 100
104 102 103 100

101

Scoring

• Subtask 1 (70% số điểm): \(n \le 10\), \(L \le 10\).
• Subtask 2 (30% số điểm): Không có ràng buộc gì thêm. (trùng global constraint)

Nam có \(n\) drone được, mỗi drone thuộc một trong hai loại: loại \(1\) và loại \(2\). Sau một buổi trình diễn, Nam tập hợp lại và xếp thành một dãy \(s_1, s_2, \ldots, s_n\), trong đó \(s_i = 1\) hoặc \(s_i = 2\) cho biết drone thứ \(i\) (\(1 \le i \le n\)) thuộc loại 1 hoặc loại 2. Nam muốn sắp xếp lại dãy drone để loại 1 xếp trước loại 2 chỉ bằng các thao tác đổi chỗ hai drone cho nhau. Cụ thể, mỗi lượt Nam có thể tráo đổi drone ở vị trí \(i\) (\(1 \le i \le n\)) với drone ở vị trí \(j\) (\(1 \le j \le n\)) cho nhau.

Yêu cầu: Hãy tính số lượt đổi chỗ hai drone ít nhất cần thực hiện để tất cả các drone loại 1 xếp trước loại 2.

Đầu vào

• Dòng đầu tiên chứa số nguyên \( n \) \((1 \le n \le 10^5\)).
• Dòng thứ hai chứa \( n \) số nguyên \( s_1, s_2, \dots, s_n \) \((1 \le s_i \le 2)\).

Đầu ra

• Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là số lần đổi chỗ hai drone ít nhất cần thực hiện.

Ví dụ

2
1 2

0

5
2 2 1 1 2

2

Cho ba số nguyên dương \(A, B, K\) (\(1 \leq A, B \leq 10^9\), \(1 \leq K \leq 15\)).

Yêu cầu: Hãy tìm số nguyên dương \(C\) nhỏ nhất sao cho tích của ba số \(𝐴, B, C\) có ít nhất \(K\) chữ số \(0\) tận cùng.

Input

• Nhập vào ba số nguyên dương lần lượt theo thứ tự là \(A, B\) và \(K\). Mỗi số viết trên một dòng.

Output

• Đưa ra một số duy nhất là số nguyên dương \(C\) thỏa mãn yêu cầu đề bài.

Scoring

• Nếu chương trình chạy đúng những trường hợp \(1 \leq A, B \leq 10^3, 1 \leq K \leq 9\), thí sinh sẽ được \(40\) điểm;
• Nếu chương trình chạy đúng những trường hợp \(1 \leq A, B \leq 10^9, 1 \leq K \leq 15\) thí sinh sẽ được \(100\) điểm

Example

15
12
2

5

Trước mặt cnn008 hiện tại có \(N\) ngọn núi, ngọn núi thứ \(i\) có độ cao là \(h_i\). cnn008 định nghĩa một dãy núi là một dãy các ngọn núi liên tiếp, mà chiều cao của các ngọn núi tăng dần cho đến đỉnh, sau đó giảm dần. Ví dụ dãy \([1, 2, 3, 2, 1]\), \([1, 2, 3]\), \([5, 3, 2]\) là các dãy núi, còn \([1, 2, 4, 2, 3]\), \([4, 4, 6, 3, 4]\) không phải là dãy núi. Nói cách khác, một dãy các ngọn núi \(h_1, h_2, \dots, h_k\) là một dãy núi khi tồn tại một chỉ số \(1 \le x \le k\) sao cho \(h_1 \le h_2 \le \dots \le h_x \ge h_{x + 1} \ge \dots h_k\).

cnn008 đang tận hưởng view triệu đô của mình, cnn008 muốn nhờ bạn trả lời \(Q\) câu hỏi. Câu hỏi thứ \(i\) gồm hai số \(l_i, r_i\), và bạn phải kiểm tra xem các ngọn núi từ \(l_i\) đến \(r_i\) có phải là một dãy núi hay không?

Input

• Dòng đầu gồm hai số nguyên dương \(N\), \(Q\).
• Dòng thứ hai gồm một dãy \(N\) số nguyên dương \(h_1, h_2, \dots, h_N\) \((1 \le h_i \le 10^9)\).
• \(Q\) dòng sau, mỗi dòng gồm hai số nguyên dương \(l_i, r_i\) \((1 \le l_i \le r_i \le N)\) là câu hỏi thứ \(i\).

Output

• In ra \(Q\) dòng, dòng thứ \(i\) là Yes nếu các ngọn núi từ \(l_i\) đến \(r_i\) là một dãy núi, ngược lại in No.

Sample Input

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

Sample Output

Yes
No
No
Yes
No

Notes

• Trong câu hỏi đầu tiên, dãy \([4]\) là một đồi núi.
• Trong câu hỏi thứ hai, dãy \([1, 2, 1, 4]\) không phải là một đồi núi.
• Trong câu hỏi thứ tư, dãy \([1, 2, 1]\) là một đồi núi.

Scoring

• Subtask \(1\) \((40\%)\): \(N, Q \le 2000\).
• Subtask \(2\) \((60\%)\): \(N, Q \le 10^5\).