У oolimry есть массив \(a\) длины \(n\), который ему очень нравится. Сегодня вы изменили его массив на \(b\), перестановку \(a\), чтобы он расстроился.
Поскольку oolimry всего лишь утка, он может выполнять только следующую операцию для восстановления своего массива:
- Выбрать два целых числа \(i,j\) таких, что \(1 \leq i,j \leq n\).
- Поменять местами \(b_i\) и \(b_j\).
Печаль массива \(b\) — это минимальное количество операций, необходимое для преобразования \(b\) в \(a\).
Для данных массивов \(a\) и \(b\), где \(b\) — перестановка \(a\), определите, имеет ли \(b\) максимальную печаль среди всех перестановок \(a\).
Выходные данные
Для каждого набора входных данных выведите «AC» (без кавычек), если \(b\) имеет максимальную печаль среди всех перестановок \(a\), и «WA» (без кавычек) в противном случае.
Примечание
В первом наборе входных данных массив \([1,2]\) имеет печаль \(1\). Мы можем преобразовать \([1,2]\) в \([2,1]\) с помощью одной операции с \((i,j)=(1,2)\).
Во втором наборе входных данных массив \([3,3,2,1]\) имеет печаль \(2\). Мы можем преобразовать \([3,3,2,1]\) в \([1,2,3,3]\) с помощью двух операций с \((i,j)=(1,4)\) и \((i,j)=(2,3)\) соответственно.
В третьем наборе входных данных массив \([2,1]\) имеет печаль \(0\).
В четвертом наборе входных данных массив \([3,2,3,1]\) имеет печаль \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
2 1
1 2
4
1 2 3 3
3 3 2 1
2
2 1
2 1
4
1 2 3 3
3 2 3 1
|
AC
AC
WA
WA
|