4729_krosh_and_string

4729. Крош и строка

Description

У Кроша есть строка, состоящая из $n$ строчных английских букв. За один ход Крош может выбрать два соседних равных символа в этой строке и удалить их, при этом получится новая строка, над которой Крош и дальше может выполнять ходы. Например, если есть строка $abccbb$, он может выбрать третий и четвертый символы и получить строку $abbb$, а затем выбрать, например, второй и третий символы из строки $abbb$ и получить строку $ab$; а может в начале из строки $abccbb$ выбрать пятый и шестой символы и получить строку $abcc$. Может ли Крош из данной строки удалить все символы?

Input Format:

В первой строке дано число $1 \le n \le 2 * 10^5$ - длина строки. В следующей строке записана сама строка, состоящая из $n$ строчных английских букв.

Output Format:

Выведите 1, если Крош может получить из данной строки пустую, и 0 иначе.

Example Test Cases

Example 1

Input:

6
abccba

Output:

1

Example 2

Input:

3
aba

Output:

0

Example 3

Input:

4
abbb

Output:

0