Дореми попросили протестировать \(n\) контестов. Контест \(i\) может быть протестирован только в день \(i\). Сложность контеста \(i\) равна \(a_i\). В начале показатель IQ Дореми равен \(q\). В день \(i\) Дореми решает, протестирует ли она контест \(i\) или нет. Она может протестировать контест только в случае, если её текущий показатель IQ строго больше \(0\).
Если Дореми решает протестировать контест \(i\) в день \(i\), то происходит следующее:
- если \(a_i>q\), то Дореми чувствует себя недостаточно умной, поэтому \(q\) уменьшается на \(1\);
- иначе ничего не изменяется.
При решении не тестировать контест ничего не происходит.
Дореми хочет протестировать как можно больше контестов. Помогите Дореми найти оптимальное решение.
Выходные данные
Для каждого набора выведите бинарную строку \(s\), где \(s_i=1\) если Дореми должна протестировать контест \(i\), и \(s_i=0\) иначе. Число единиц в строке должно быть максимально возможным, и при этом она не должна тестировать контест, когда её показатель IQ меньше либо равен нулю.
Если существуют несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных Дореми тестирует единственный имеющийся контест. Её показатель IQ не уменьшается.
Во втором наборе входных данных Дореми тестирует оба имеющихся контеста. Её показатель IQ уменьшается на \(1\) после тестирования контеста \(2\).
В третьем наборе входных данных Дореми тестирует контесты \(1\) и \(2\). Её показатель IQ уменьшается до \(0\) после тестирования контеста \(2\), поэтому она не может протестировать контест \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 1
1
2 1
1 2
3 1
1 2 1
4 2
1 4 3 1
5 2
5 1 2 4 3
|
1
11
110
1110
01111
|