REPLACARR

Xem PDF
Tác giả:
dang7rickroll
Dạng bài
Điểm: 150 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số nguyên dương \(a_1,a_2,…,a_n\). Hãy tìm cách thay thế một giá trị \(a_i\) nào đó bằng một giá trị khác có trong dãy sao cho số lượng các phần tử bằng nhau trong dãy là chẵn.

Input

  • Dòng đầu ghi số nguyên dương \(n\) \((n \le 25000)\)
  • Dòng thứ hai ghi ra \(n\) số nguyên dương \(a_1,a_2,..,a_n\) \((a_i \le 25000)\)

Output

  • Số cách thay thế. Nếu không thể thay thế, in ra -1.

Example

Test 1

Input 
4
0 1 0 2
Output 
1
Note

Ta thay thế phần tử \(1\) bằng phần tử \(2\) hoặc thay thế phần tử \(2\) bằng phần tử \(1\). Hai cách này đều được tính là \(1\) cách.

Test 2

Input 
3
0 0 0
Output 
-1
Note

Do chỉ có 3 phần tử bằng nhau, không thể tạo thành các phần tử có số lượng chẵn, vì vậy đáp án là \(-1\).

Test 3

Input 
4
1 2 3 4
Output 
2
Note

Với phần tử \(1\), ta có các cách: thay \(1\) bằng \(2\), thay \(1\) bằng \(3\), thay 1 bằng \(4\), tuy nhiên, tất cả đều chỉ được tính là \(1\) cách.

Lưu ý:

  • Bạn được phép thay đổi 2 phần tử khác nhau cùng 1 lúc.

Bình luận