Thần bài người Italy 2

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Một thần bài người Italy đang chơi một trò chơi với những lá bài. Bộ bài gồm n lá bài được đánh số từ \(1\) đến \(n\). Anh ấy bốc \(k\) lá bài bất kì từ bộ bài và trải dài ra sàn nha. Để phục vụ cho thiết kế ảo thuật, anh ấy muốn thay \(1\) lá bài nhỏ nhất trên sàn nhà bằng \(1\) lá bài lớn nhất trong những lá bài còn lại của bộ bài.

Vị thần bài này muốn thực hiện phép thay đổi này \(q\) lần. Hãy tính xem sau khi thay \(q\) lần, tổng lá bài trên sàn là bao nhiêu.

Input

  • Dòng đầu tiền gồm \(n\), \(k\)\(q (k < n)\).
  • Dòng tiếp theo gồm \(k\) số nguyên dương khác nhau \(A_i (1 \leq A_i \leq n)\).

Output

  • Gồm 1 dòng duy nhất là kết quả bài toán.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(2 \leq n,q \leq 10^3\)
  • Subtask \(2\) (\(30\%\) số điểm): \(2 \leq n,q \leq 2 \times 10^5\)
  • Subtask \(3\) (\(40\%\) số điểm): \(2 \leq n \leq 2 \times 10^2, q \leq 10^9\)

Example

Test 1

Input
5 2 3
1 3 
Output
8

Bình luận

Không có bình luận nào.