An có một mảng gồm \(N-1\) số nguyên. Các số này thuộc tập \(\{1, 2, ..., N\}\) và không trùng nhau. Như vậy có đúng 1 số bị thiếu trong đoạn \([1, N]\).

Hãy dùng tìm kiếm nhị phân để tìm số bị thiếu.

Gợi ý: Sắp xếp mảng trước. Nếu mảng \(a\) đã sắp xếp, thì \(a[i] = i+1\) với mọi \(i\) đứng trước số bị thiếu.

Input:

• Dòng 1: \(N\) (\(2 \le N \le 10^5\))
• Dòng 2: \(N-1\) số nguyên phân biệt (\(1 \le a_i \le N\))

Output: Số nguyên duy nhất bị thiếu.

Ví dụ: Input:

5
1 2 4 5

Output:

3