# 18353 - 병사배치하기

> <https://www.acmicpc.net/problem/18353>

* LIS (가장 긴 증가하는 부분순열) 문제이다.
* [LIS](https://pyohamen.gitbook.io/til/algorithm/implementation/dynamic_programming) 에 핵심적인 점화식 개념을 써놓았다.

```python
n = int(input())
a = list(map(int,input().split()))
d = [1] * n

for i in range(n):
    for j in range(i):
        if a[j] > a[i]:
            d[i] = max(d[j] + 1, d[i])

print(n - max(d))
```