1-3. 영화 관람 ★★★☆☆

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, idx, max = 0;
	cin >> n;
	
	vector<int> V(n+1, 0);
	vector<int> ans(n+1, 0);
	
	for(int i = 1; i <= n; i++)
	{
		cin >> V[i];
	}
	
	ans[1] = 0;
	
	for(int i = 2; i <= n; i++)
	{
		int temp = V[i];
		if(temp < V[i-1])
		{
			ans[i] = i-1;
		}
		else
		{
			if(ans[i-1] != 0)
			{
				int idx = ans[i-1];
				while(idx != 0)
				{
					if(temp < V[idx])
					{
						ans[i] = idx;
						break;
					}
					else
					{
						idx = ans[idx];
					}
				}
			}
		}
	}
	
	for(int i = 1; i <= n; i++)
		cout << ans[i] << " ";
		
	return 0;
	
}

1. 맨 앞 학생은 방해하는 사람이 없으므로 0이다.

2. 2번째 학생부터 자신의 앞사람과의 크기를 비교한다. 앞사람이 더 크다면 그 사람이 방해하는 사람이므로 그 사람의 번호를 ans[i] 에 할당한다.

3. 앞사람이 작다면 앞사람을 방해하는 사람과 비교한다. 그 사람과 비교했을 때도 작다면 그 사람을 방해하는 사람과 비교한다. 이렇게 비교해가면서 크거나 같은 사람을 만나거나 방해하는 사람이 없을 때까지 반복한다.