백준_1539

#include <bits/stdc++.h>
using namespace std;

set <int> s;
int heights[250002];
long long sum = 0;

int main(void) {
    int n;
    cin >> n;

    while (n--) {
        int value;
        cin >> value;

        auto iter = s.lower_bound(value);

        long long left, right;
        
        if (iter != s.begin()) {
            auto left_iter = iter;
            left = heights[*(--left_iter)];
        } else {
            left = 0;
        }

        if (iter != s.end()) {
            right = heights[*iter];
        } else {
            right = 0;
        }

        heights[value] = max(left, right) + 1;
        s.insert(value);

        sum += heights[value];
    }

    cout << sum << endl;
}

이 코드는 많이 어려웠다...
복습 필수다..필수!!!!!
(결과는 맞았지만 거의 내가 풀었다기 보다 구글이 풀어준 터라... 이미지는 첨부하지 않았다)