#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;

int n;
int item_cnt = 0;
int category_cnt;
vector<string> v;
int s_idx = 0;
int e_idx = 0;
map<string, int> m;
set<string> s;

/*
void get_start_window(){
	int isFind = false;
	int idx = s_idx;
	while(!isFind){
		m[v[idx]] -= 1;
		if(m[v[idx]] == 0){
			item_cnt -= 1;
		}
		if(item_cnt != category_cnt){
			m[v[idx]] += 1;
			item_cnt += 1;
			s_idx = idx;
			isFind = true;
		}
		idx++;
	}
}
*/

void get_end_window(){
	while(e_idx < n){
		//cout << idx << endl;
		m[v[e_idx]] += 1;
		if(m[v[e_idx]] == 1){
			item_cnt += 1;
		}
		if(item_cnt == category_cnt){
			break;
		}
		e_idx++;
	}
	
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int s_ans, e_ans, w_size;

	bool isBuy = false;
	cin >> n;
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		v.push_back(s);
		if(m.find(s) == m.end()){
			m.insert({s,0});
		}
		
		
	}
	
	category_cnt = m.size();
	//슬라이딩 윈도우의 끝 지점을 찾는다.
	get_end_window();
	s_ans = s_idx;
	e_ans = e_idx;
	w_size = e_ans - s_ans;
	while(e_idx < n){
		//cout << s_idx << " " << e_idx << endl;
		string item = v[s_idx];
		m[item]--;
		s_idx++;
		if(m[item] == 0){
			item_cnt--;
			e_idx++;
			get_end_window();
		}
		
		
		if(item_cnt == category_cnt && w_size > e_idx - s_idx){
					s_ans = s_idx;
					e_ans = e_idx;
					w_size =  e_ans - s_ans;
			}	

		
	}
	
	cout << s_ans + 1 << endl << e_ans + 1;
	
	
	
	
	return 0;
}

#include <iostream>
#include <set>

using namespace std;

int slope[502][502];
int cases[502][502];
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
int M, N;

bool is_available(int x, int y, int i) {
	bool res = false;

	if (x + dir[i][0] > 0 && x + dir[i][0] <= M && y + dir[i][1] > 0 && y + dir[i][1] <= N) {		
		res = true;
	}

	return res;
}
int getload(int x, int y) {
	int res = 0;
	bool found = false;
	//cout << "x: " << x << ", y: " << y << "\n";
	if (cases[x][y] != -1) {
		//cout << cases[x][y] << "\n";
		return cases[x][y];
	}

	if (x == M && y == N) {
		return 1;
	}

	for (int i = 0; i < 4; i++) {
		if (is_available(x, y, i)) {
			if (slope[x][y] > slope[x + dir[i][0]][y + dir[i][1]]) {
				res += getload (x + dir[i][0], y + dir[i][1]);
			}
			
		}
	}

	//cout << res << "\n";
	cases[x][y] = res;
	return res;
}
int main() {
	cin >> M >> N;
	for (int i = 1; i <= M;i++) {
		for (int j = 1; j <= N; j++) {
			cin >> slope[i][j];
			cases[i][j] = -1;
		}
	}

	cout << getload(1, 1);
}

#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define pii pair<int, int>
#define abs(a) (a>0?a:-a)

int n, weights[200000], a, b, res;
bool visited[200000]={1};
vector<vector<int>> tree(200000, vector<int>());
queue<int> bfsQueue;
stack<pii> calcEdges;
int main()
{
    scanf("%d",&n);
    for(int cnt=0; cnt<n; ++cnt)
        scanf("%d",&weights[cnt]);
     
    for(int cnt=1; cnt<n; ++cnt){
        scanf("%d%d",&a,&b);
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    
    bfsQueue.push(0);
    while(!bfsQueue.empty()){
        int node = bfsQueue.front(); bfsQueue.pop();
        for(int cnt=0; cnt<tree[node].size(); ++cnt){
            int nextNode = tree[node][cnt];
            if(!visited[nextNode]){
                ++visited[nextNode]; 
                bfsQueue.push(nextNode);
                calcEdges.push(make_pair(node, nextNode));
            }
        }
    }
    
    while(!calcEdges.empty()){
        int pNode =calcEdges.top().first, cNode = calcEdges.top().second;
        calcEdges.pop();
        res += abs(weights[cNode]), weights[pNode] += weights[cNode];
    }
    
    printf("%d", weights[0]?-1:res);
    return 0;
}

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

struct Process {
	int PID;
	long long int ExecTime;

	bool operator<(Process _other) const {

		if (this->ExecTime == _other.ExecTime) {
			return this->PID > _other.PID;
		}
		else return this->ExecTime > _other.ExecTime;
		
	}
};
class RR {
private:
	priority_queue<Process> Table;
	vector<int>run;
	vector<int>remainTime;
	long long curTime=0;
	int totallen;
	int len;

public:

	long long int getPID(long long k) {
		Process curP;
		bool found = false;
		long long res;
		long long int clear_iter, prev_iter = 0;
		while (true) {
			curP = Table.top();
			clear_iter = curP.ExecTime;

			if (curTime + (clear_iter - prev_iter) * len > k)
				break;
			else curTime += (clear_iter - prev_iter) * len;
			Table.pop();
			len--;

			prev_iter = clear_iter;

		}
		vector<int>remain;
		while (!Table.empty()) {
			curP = Table.top();
			Table.pop();
			remain.push_back(curP.PID);

		}

		sort(remain.begin(), remain.end());
		res = remain[(k - curTime) % remain.size()];
		return res;

	}
	void getTimes_io() {
		int n,  timeInput;
		long long k,sum = 0;
		cin >> n >> k;
		len = n;
		totallen = n;
		for (int i = 0; i < n; i++) {			
			Process pInput;
			
			cin >> timeInput;
			pInput.PID = i;
			pInput.ExecTime = timeInput;
			sum += timeInput;

			Table.push(pInput);
			run.push_back(i);
			remainTime.push_back(timeInput);
		}
		if (sum <= k) {
			cout << -1;
		}
		else
			cout << getPID(k);
	}

};


int main() {
	RR table;
	table.getTimes_io();
}

#include <cstdio>
#include <algorithm>
using namespace std;

int cardCnt[100001], minPoint=100001, maxPoint, n, k, cardNum, sum;

int main(){
	scanf("%d%d",&n,&k);
	for(int cnt=0;cnt<n;++cnt){
		scanf("%d", &cardNum);
		++cardCnt[cardNum];
		minPoint = min(minPoint, cardNum);
		maxPoint = max(maxPoint, cardNum);
		sum+=cardNum;
	}
	
	for(int cnt=1;cnt<=k;++cnt){
		if(cnt&1){
			while(!cardCnt[minPoint]) ++minPoint;
			sum-=minPoint;
			--cardCnt[minPoint];
		}
		else{
			while(!cardCnt[maxPoint]) --maxPoint;
			sum-=maxPoint;
			--cardCnt[maxPoint];
		}
	}
	printf("%d",sum);
	return 0;
}

#include <cstdio>

unsigned long long result=1;
int n;

//1 <= n <= 62 계산 가능
//식은.. 원반이 처음에 위치한 자리에 따리 거쳐가는 막대의 경로가 같기 때문에
//그것을 이용한 O(1)의 일반향입니다.. f(n) = n + 2^(n+1) - 2

int main() {
	scanf("%d",&n);
	result<<=n+1;
	printf("%llu",n+result-2);
	return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;

#define INT_MAX (1<<31)-1

//n,k,stones는 입력받는 값을 저장할 변수, rangeMaxTree, pnt(=point)는 세그먼트 트리를 구현하기 위한 변수 / <<X는 *(2의 X제곱)과 같음.
int n,k,stones[200020], rangeMaxTree[1<<21], pnt=1;

//세그먼트 트리를 업데이트 하는 함수
void update(int node, int value){
	//node에 point를 더해 세그먼트 트리의 리프노드를 향하게 만들고
	//리프노드는 구간이 하나니까 max값을 계산하는 대신 값을 그대로 저장함
	node += pnt; 
	rangeMaxTree[node] = value;
	
	//그 뒤로 루트노드까지 노드의 부모노드를 방문해서 max값을 재계산함.
	while(node/=2)
		rangeMaxTree[node] = max(rangeMaxTree[node*2], rangeMaxTree[node*2+1]); 
}

int getRangeMax(int srt, int end){
	//구간의 시작과 끝점에 point를 더해 세그먼트 트리의 리프노드를 향하게 만듦 + 초기값 세팅
	srt += pnt, end += pnt;
	int maxNum = 0;
	
	//리프노드들부터 올라가면서 구간의 max값을 구함.
	while(srt<=end){
		
		//start가 홀수일 때 더 이상 합칠 구간이 없으므로 max값에 반영 후 start 한 칸 오른쪽으로 이동
		if(srt&1) maxNum = max(maxNum,rangeMaxTree[srt++]);
		
		//end가 짝수일 때 더 이상 합칠 구간이 없으므로 max값에 반영 후 end 한 칸 왼쪽으로 이동
		if(!end&1) maxNum = max(maxNum, rangeMaxTree[end--]);
		
		//start와 end 모두 부모노드로 올라감. >>=X는 /=(2의 X제곱)과 같음.
		srt>>=1, end>>=1;
	}
	return maxNum;
}


// 알고리즘
// n번째 징검다리에서 건널 수 있는 최대 인원수 = (n-k~n-1번째 징검다리에서 건널 수 있는 최대 인원수) 와 (n번째 징검다리에서 건널 수 있는 인원수) 중 최솟값
// 이라 생각하고 구현했습니당
// 세그먼트 트리는 이 때 [n-k,n-1] 구간의 최댓값을 빨리 구하려고 만드는 것

int main(){
	scanf("%d%d",&n,&k);
	for(int cnt=1; cnt<=n; ++cnt)
		scanf("%d", &stones[cnt]);
	
	//point가 가리킬 위치를 계산하는 것, 세그먼트 트리를 완전 이진 트리로 만들어서 계산에 용이하도록 만듦 
	while(pnt<=n) pnt<<=1;
	
	
	update(0, INT_MAX);//INT_MAX는 #define 참고, 처음(0번째 징검다리 = 지상)에는 무제한으로 건너올 수 있으니까 반영함
	for(int dpCnt=1; dpCnt<=n; ++dpCnt){
		//maxNum : 구간 중 건널 수 있는 최대 인원수, possibleMember = dpCnt번째 징검다리에서 건널 수 있는 최대 인원수
		int maxNum = getRangeMax(max(0,dpCnt-k), dpCnt-1),
			possibleMember = min(stones[dpCnt], maxNum);
		
		//다음 계산을 위해 세그먼트 트리에 반영
		update(dpCnt, possibleMember);
		
		//한 줄로 바꾸면 아래가 됨
		//update(dpCnt, min(getRangeMax(max(0,dpCnt-k),dpCnt-1), stones[dpCnt]));
	}
	
	//도착지점에서의 구간 최댓값을 구하면 원하는 결과를 얻을 수 있음
	printf("%d",getRangeMax(n-k+1,n));
	return 0; 
}

#include <cstdio>

#define max(a,b) (a>b?a:b)

//sumCookies : 1~n까지 쿠키의 누적합
int n, cookie, sumCookies[2001], res;

//[a,b], [b+1,c]중 b를 담당하는 이진 탐색
//a,c가 정해져 있으면 각 구간의 합이 동일하게 만드는 b는 여러개라도 동일한 구간의 합의 값은 단 1개이다.
//또한 f(x) = [a,x] - [x+1,c]로 두면 f(x)는 증가함수 이므로 이를 이용해 이진탐색이 가능하다.
int binary_search(int eLeft, int eRight){
	
	//rSum = [1,eRight] - [1,eLeft], 즉, [1,c] - [1,a-1] = [a,c] // mid가 b의 역할을 함
	int left = eLeft+1, right = eRight, mid, lSum, rSum = sumCookies[eRight]-sumCookies[eLeft];
	
	while(left<=right){
		//lSum = [1,b] - [1,a-1] = [a,b]
		mid = (left+right)/2, lSum = sumCookies[mid]-sumCookies[eLeft];
		
		//[a,b] == [b+1,c] ==> [a,b] == [a,c]-[a,b] ==> 2*[a,b] == [a,c]
		if(2*lSum == rSum) return lSum;
		else if(2*lSum > rSum) right = mid-1;
		else left = mid+1;
	}
	return -1;
}

int main() {
	scanf("%d",&n);
	//[a,b], [b+1,c]중 c를 담당하는 for문
	for(int cnt=1; cnt<=n; ++cnt){
		scanf("%d",&cookie);
		//값을 입력 받으면서 바로 구간합을 갱신함
		sumCookies[cnt] = sumCookies[cnt-1]+cookie;
		
		//[a,b], [b+1,c]중 a를 담당하는 for문, srtBasket == a-1임
		for(int srtBasket = 0; srtBasket<cnt; ++srtBasket){
			//binary search를 이용해서 구간의 합을 찾고 답을 갱신함
			res = max(res, binary_search(srtBasket, cnt));
		}
	}
	
	printf("%d", res);
	
	return 0;
}

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

vector<string> words;
const int MAX = 99999999;
int dp[20005];
int main(){
	int n;
	string str;
	cin >> n;

	cin >> str;
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		words.push_back(s);
	}
	
	for(int i = 1; i <= str.length(); i++){
		dp[i] = MAX;
	}
	
	for(int i = 1; i <= str.length(); i++){
		for(int j = 0; j < words.size(); j++){
			string s = words[j];

			if(i - s.length() < 0){
				continue;
			}
			bool flag = true;
			for(int k = 0; k < s.length(); k++){
				if(s[k] != str[i - s.length() + k]){
					flag = false;
					break;
				}
			}
			if(flag){
				dp[i] = min(dp[i], dp[i - s.length()] + 1);
			}
		}
	}
	int ans = dp[str.length()];
	if(ans == MAX){
		cout << -1;
	}else{
		cout << ans;
	}
	return 0;
}

//Trie + DP로 풀기
#include <cstdio>
#include <cstring>
#define min(a,b) (a<b?a:b)

class Trie{
public:
    Trie* abt[26];
    bool isEnd; //끝난지점을 확인하기 위해 변수 추가
	
    Trie(){
        memset(abt, 0, sizeof(abt));
		isEnd=false;
    }
    
    ~Trie(){
        for(int cnt=0; cnt<26; ++cnt)
            if(abt[cnt]) delete abt[cnt];
    }
    
    Trie* insert(int ch){
        if(!abt[ch-='a'])
			abt[ch] = new Trie();
        return abt[ch];
    }
};

//wordDp[n] : n-1번째 문자열을 완성하는데까지 사용한 단어의 최소 개수
int n, wordDp[20010], cnt, len, cur;
char str[20010], word[6];
Trie root;
Trie* trie;

int main(){
	scanf("%d",&n); getchar();
	scanf("%s", str);
	for(cnt=0; cnt<n; ++cnt){
		scanf("%s",word);
		trie = &root;
		
		//단어를 트라이 자료구조에 넣음
		for(cur=0; word[cur]; ++cur)
			trie = trie->insert(word[cur]);
		
		//단어의 마지막 알파벳 위치에 단어가 끝났다는 것을 저장함
		trie->isEnd = true;
	}
	
	//DP 초기값 설정
	for(cnt=1; cnt<=20000; ++cnt)
		wordDp[cnt] = 1<<30;
	
	for(len=0; str[len]; ++len){
		trie = &root, cur=len;
		
		//문자열이 끝나지 않았고 트라이에 str[cur]에 해당하는 알파벳이 없을 때까지 반복
		while(str[cur] && (trie = trie->abt[str[cur++]-'a'])){
			
			//단어가 끝났다면 DP값을 갱신함
			if(trie->isEnd) wordDp[cur] = min(wordDp[cur], wordDp[len]+1);
		}
	}
	
	//주어진 단어들로 문자열을 만들 수 없다면 -1, 아니면 dp값을 출력함
	printf("%d", wordDp[len]==(1<<30)?-1:wordDp[len]);
	return 0;
}

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

//dp[n] : n을 루트로 하는 서브 트리에서 ([0] : n을 포함하지 않고, [1] : n을 포함하고) 서브 트리의 모든 팀을 참여시킬 때의 매출액의 최솟값
int n, sales[300001], leader, member, dp[300001][2];
vector<vector<int>> tree(300001,vector<int>());
stack<pair<int, int>> funcStack;

int main(){
	scanf("%d",&n);
	for(int cnt=0;cnt<n;++cnt)
		scanf("%d",&sales[cnt]);
	
	for(int cnt=1;cnt<n;++cnt){
		scanf("%d%d",&leader,&member);
		tree[leader].push_back(member);
	}
	
	//재귀함수 대신 funcStack 사용
	funcStack.push(make_pair(0,0));
	while(!funcStack.empty()){
		int leader = funcStack.top().first, mode = funcStack.top().second;
		funcStack.pop();
		
		//mode가 0일 때는 재귀적으로 각 서브 트리로 진입함
		if(!mode){
			funcStack.push(make_pair(leader,1));
			for(int cnt=0;cnt<tree[leader].size();++cnt)
				funcStack.push(make_pair(tree[leader][cnt],0));
		}
		
		//mode가 1일 때 팀원노드들은 모두 계산이 완료되어 있으므로 팀장노드를 계산함
		else{
			//팀장 노드가 들어갈 때(dp[leader][1])는 항상 팀장의 팀이 들어가니까
			//팀원들이 들어가든 말든 상관없이 (팀원하위팀 매출액 최솟값의 합 + 팀장 매출액) 이 최솟값이 됨

			//팀장 노드가 들어가지 않을 때(dp[leader][0])는 팀원 1명 이상이 무조건 들어가 있어야 하니
			//sumMembers를 이용해서 예외상황을 처리함
			int sumMembers = 0;
			for(int cnt=0; cnt<tree[leader].size(); ++cnt){
				member = tree[leader][cnt];
				dp[leader][0] += min(dp[member][0], dp[member][1]), sumMembers += dp[member][0];
			}
			dp[leader][1] = dp[leader][0]+sales[leader];
			
			//dp[leader][0]은 현재 (팀원하위팀 매출액 최솟값의 합)이기 때문에 이게 sumMembers이랑 같다는 건
			//팀원이 한명도 들어가 있지 않다고 추측할 수 있음
			if(tree[leader].size() && dp[leader][0] == sumMembers){
				
				//따라서 팀원을 한 명씩 넣어보면서 최솟값을 갱신함 
				dp[leader][0] = (1<<31)-1;
				for(int cnt=0; cnt<tree[leader].size(); ++cnt){
					member = tree[leader][cnt];
					dp[leader][0] = min(dp[leader][0], sumMembers-dp[member][0]+dp[member][1]);
				}
			}
		}
	}
	
	//CEO가 들어간 최솟값과 제외한 최솟값 중 더 작은 값을 출력함
	printf("%d", min(dp[0][0], dp[0][1]));
	return 0;
}

#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int main() {
	int n, k, num;
	queue<int> moves;
	stack<int> stk;

	cin >> n >> k;
	vector<queue<int>> board(n + 1);

	for (int i = 0; i < k; i++)
	{
		cin >> num;
		moves.push(num);
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> num;
			if (num) board[j].push(num);
		}
	}

	int top, total = 0;
	while (!moves.empty()) {
		num = moves.front();
		moves.pop();
		if (!board[num].empty()) {
			if (stk.empty()) top = 0;
			else top = stk.top();

			if (top == board[num].front() && !stk.empty()) {
				stk.pop();
				total += 2;
			}
			else {
				stk.push(board[num].front());
			}
			board[num].pop();
		}
	}
	cout << total;
	return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

struct Times
{
	int start;
	int end;
};

bool schedule(Times x, Times y) {
	if (x.end != y.end)
		return x.end < y.end;
	else
		return x.start < y.start;
}

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

	Times* times = new Times[n];
	for (int i = 0; i < n; i++) {
		cin >> times[i].start >> times[i].end;
	}
	sort(times, times + n, schedule);

	int count = 0;
	int end = -1;

	for (int i = 0; i < n; i++) {
		if (times[i].start >= end) {
			count++;
			end = times[i].end;
		}
	}

	cout << count << endl;

	return 0;
}

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

#define pii pair<int, int>

int n, board[102][102], temp, robotBoard[102][102][2], dx[]={1,-1,0,0}, dy[]={0,0,1,-1};
queue<pair<pii, pii>> bfsQueue;

int main()
{
    scanf("%d",&n);
    for(int row=1; row<=n; ++row)
        for(int col=1; col<=n; ++col){
            scanf("%d",&temp);
            //board에서 0을 장애물로 이용하기 위해 입력받은 값에서 0->1, 1->0으로 바꿔서 저장함
            //이후로 1이 빈칸, 0이 장애물이 됨
            //이 방법을 쓰면 저장되지 않은 board의 모든 칸이 장애물로 인식되어 따로 벽 처리해주지 않아도 됨
            board[row][col] = !temp;
        }
    
    //robotBoard는 모두 0으로 초기화되어 있기 때문에 초기값과 방문값에 차이를 두기 위해 첫 좌표를 1로 설정함
    //앞으로 0이면 방문하지 않은 좌표, 0이 아니면 방문했던 좌표가 됨
    robotBoard[1][1][0] = 1;
    bfsQueue.push(make_pair(make_pair(1,1),make_pair(1,2)));
    
    //로봇의 왼쪽/위쪽 팔이 있는 좌표가 값을 저장할 좌표가 됨
    //따라서 bfsQueue에 새로운 좌표를 넣을 때는 항상 first가 왼쪽/위쪽 팔의 좌표가 되도록 넣어야 함
    while(!bfsQueue.empty()){
        //mode는 0일 때 가로, 1일 때 세로를 뜻함. lu = left/up, rd = right/down, n = next를 뜻함
        pii luPos = bfsQueue.front().first, rdPos = bfsQueue.front().second;
        int lux = luPos.first, luy = luPos.second, rdx = rdPos.first, rdy = rdPos.second,
            mode = luy == rdy, val = robotBoard[lux][luy][mode]+1;
        bfsQueue.pop();
        
        //cnt 0:아래쪽이동, 1:위쪽이동, 2:오른쪽이동, 3:왼쪽이동
        for(int cnt=0; cnt<4; ++cnt){
            int lunx = lux + dx[cnt], luny = luy + dy[cnt],
                rdnx = rdx + dx[cnt], rdny = rdy + dy[cnt];
            pii lunPos = make_pair(lunx,luny), rdnPos = make_pair(rdnx,rdny);
            
            //로봇이 이동할 좌표가 모두 빈칸(=1)이라면
            if(board[lunx][luny] && board[rdnx][rdny]){
                
                //상하좌우용 코드
                //다음 좌표를 방문하지 않았다면 방문값을 저장하고 bfsQueue에 넣음
                if(!robotBoard[lunx][luny][mode]){
                    robotBoard[lunx][luny][mode] = val;
                    bfsQueue.push(make_pair(lunPos,rdnPos));
                }
            
                //회전용 코드
                //로봇이 가로모드일 때 상/하로 이동할 수 있으면 좌상,우상/좌하,우하로 회전할 수 있음
                //로봇이 세로모드일 때 좌/우로 이동할 수 있으면 좌상,좌하/우상,우하로 회전할 수 있음
                //cnt<=1 : 상하이동, cnt>1 : 좌우이동, !mode : 세로모드, mode : 가로모드
                if(cnt/2 == mode){ // == (cnt>1 && mode) || (cnt<=1 && !mode)
                    if(cnt%2){ //(cnt, mode) : (1,0), (3,1)
                        
                        //로봇이 위쪽/왼쪽으로 이동했을 때는 원래 좌표보다 이동한 좌표가 더 작기 때문에 이동한 좌표를 기준으로 방문 여부를 확인함
                        if(!robotBoard[lunx][luny][!mode]){
                            robotBoard[lunx][luny][!mode] = val;
                            bfsQueue.push(make_pair(lunPos, luPos));
                        }
                        if(!robotBoard[rdnx][rdny][!mode]){
                            robotBoard[rdnx][rdny][!mode] = val;
                            bfsQueue.push(make_pair(rdnPos, rdPos));
                        }
                    }
                    else{ //(cnt,mode) : (0,0), (2,1)
            
                        //로봇이 아래쪽/오른쪽으로 이동했을 때는 원래 좌표가 이동한 좌표보다 더 작기 때문에 원래 좌표를 기준으로 방문 여부를 확인함
                        if(!robotBoard[lux][luy][!mode]){
                            robotBoard[lux][luy][!mode] = val;
                            bfsQueue.push(make_pair(luPos, lunPos));
                        }
                        if(!robotBoard[rdx][rdy][!mode]){
                            robotBoard[rdx][rdy][!mode] = val;
                            bfsQueue.push(make_pair(rdPos, rdnPos));
                        }
                    }
                    //if-else 없이 min,max 처리하면 코드 수가 줄어들지만, 보기 힘들까봐 min,max처리는 하지 않음
                }
            }
        }
    }
    
    //(n,n)에 로봇이 걸치는 가로 좌표(n,n-1), 세로 좌표(n-1,n) 중 더 작은 값을 출력함
    //0이면 10억을 반환해서 선택되지 않도록 하고 로봇의 시작점을 1로 잡았으니 1을 빼줌
    printf("%d",min(robotBoard[n][n-1][0]?robotBoard[n][n-1][0]:1<<30,robotBoard[n-1][n][1]?robotBoard[n-1][n][1]:1<<30)-1);
        
    return 0;
}

//solving with union-find, backtracking : 80ms
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;

#define max(a,b) (a>b?a:b)

int n, v, left, right, leftGroup[100002], rightGroup[100002], disFromRoot[100002];
long long res;
stack<int> vStack;
stack<pair<int,pair<int,int>>> rangeStack;

int findLeft(int num){
    if(leftGroup[num] == num) return num;
    else return leftGroup[num] = findLeft(leftGroup[num]);
}

int findRight(int num){
    if(rightGroup[num] == num) return num;
    else return rightGroup[num] = findRight(rightGroup[num]);
}

//알고리즘 배경
//이진트리의 빠른 삽입은 삽입하고자 하는 값과 가장 가까이에 있는 값 중 비어있는 가지에 넣는 것이다.
//예시로 이진트리 안에 1 6 4 2 순으로 넣었다면 5를 넣을 때는 4와 6 중에 비어있는 가지인 4오른쪽에 넣고(6왼쪽에는 4가 들어가 있다)
//5가 들어간 후 3을 넣는다면 2와 4 중에 비어있는 가지인 2의 오른쪽에 넣는 것이다.(4왼쪽에는 2가 들어가 있다)
//여기서 문제는 '삽입하고자 하는 값과 가장 가까운 두 수를 어떻게 얻을 것인가' 이다.
//만약 O(1)만에 값을 얻고자 가장 가까운 두 수를 저장하는 배열을 만들었다고 해보자.
//초기에는 배열1은 모드 0으로 초기화 되어 있고, 배열2는 n+1로 초기화 되어 있을 것이다.
//하지만 값을 삽입한 뒤, 배열1은 [값,n]구간을 값으로 업데이트하고, 배열2는 [1,값]구간을 값으로 업데이트하면 시간적 손실이 굉장히 많이 나게 된다.
//여기서 두 배열은 모든 값을 삽입한 후 (배열[값] == 값) 이라는 특성을 이용해 백트래킹을 진행한다.
int main()
{
    scanf("%d",&n);
    for(int cnt=0;cnt<n;++cnt){
        scanf("%d",&v);
        vStack.push(v);
    }
    
    //union-find 초기 세팅, 여기서 자기자신을 가리킨다는 건 이진트리에 삽입되어 있음을 의미함
    for(int cnt=0;cnt<=100001;++cnt)
        leftGroup[cnt] = rightGroup[cnt] = cnt;
    
    while(!vStack.empty()){
        v = vStack.top(); vStack.pop();
        
        //자신과 가장 가까이에 있는 왼쪽값과 오른쪽 값을 구함
        left = findLeft(v-1), right = findRight(v+1);
        
        //자신은 이제 트리에 없는 값이 될 것이므로 자신을 가리키지 않도록 왼쪽과 오른쪽 값을 저장함
        leftGroup[v] = left, rightGroup[v] = right;
        
        //재귀함수 스택 오버플로우 방지용
        //[v,right-1], [left+1,v] 구간에 있는 모든 값은 모두 이진트리에 없기 때문에 이를 이용해 배열을 업데이트 함
        findLeft(right-1), findRight(left+1);
        
        //삽입할 값과 가장 가까운 왼쪽값, 오른쪽값을 스택에 저장함
        rangeStack.push(make_pair(v,make_pair(left,right)));   
    }
    
    while(!rangeStack.empty()){
        v = rangeStack.top().first, left = rangeStack.top().second.first, right = rangeStack.top().second.second;
        rangeStack.pop();
        
        //구간 중 루트와 거리가 더 먼 노드를 채택해 v노드에 기록하고 result에 높이를 반영함
        res+=(disFromRoot[v] = max(disFromRoot[left], disFromRoot[right])+1)-1;
        
        printf("%lld\n",res);
    }
    return 0;
}

/*
이진 탐색 트리
N의 크기는 10만
C의 값은 곧 랭크 누적
매번 insert 함수를 수행한다면
시간복잡도는 O(N)이므로 수행 시간을 보장할 수 없다.
또한 최악의 경우 편향 이진 트리가 될 수 있어 O(N^2)
이진탐색트리 삽입 원리를 이해하자
*/

#include <iostream>
#include <map>
#include <utility>
#include <algorithm>

using namespace std;

map<int, int> m;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int n;
	cin >> n;
	long long C = 0;
	int depth;
	
	/*
	최대 최소 값 처리 테크닉
	*/
	m.insert({0,-1});
	m.insert({100005, -1});
	
	for(int i = 0; i < n; i++){
		int num;
		cin >> num;
		auto up_iter = m.upper_bound(num);
		auto low_iter = up_iter;
		--low_iter;//후위 연산자를 사용하면 이전 값을 반환하기 때문에 임시 객체가 생겨 성능이 낮아진다고 함.
		depth = max(up_iter->second, low_iter->second) + 1;
		m.insert({num, depth});
		C += depth;
		cout << C << '\n';
	}
	return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

#define pii pair<int,int>

int n, st, ed, segTree[1<<21], ptr=1<<20;
vector<pii> timetable;
vector<int> computers, endTimes;
map<int,priority_queue<int>> timeComputer;

void update(int num, int val){
    segTree[num+=ptr] = val;
    while(num>>=1)
        segTree[num] = min(segTree[num*2], segTree[num*2+1]);
}

int getMin(int st, int ed){
    st+=ptr, ed+=ptr;
    int res = 1000001;
    while(st<=ed){
        if(st%2==1) res = min(res, segTree[st]), ++st;
        if(ed%2==0) res = min(res, segTree[ed]), --ed;
        st>>=1, ed>>=1;
    }
    return res;
}

int main()
{
    scanf("%d",&n);
    for(int cnt=0; cnt<n; ++cnt){
        scanf("%d%d",&st,&ed);
        timetable.push_back(make_pair(st,ed));
    }
    
    sort(timetable.begin(), timetable.end());
    fill(segTree, segTree+ptr*2, 1000001);
    
    for(auto iter = timetable.begin(); iter != timetable.end(); ++iter){
        int minPos = getMin(0, iter->first);
        if(!timeComputer.count(iter->second))
            timeComputer.insert(make_pair(iter->second, priority_queue<int>()));
        
        
        if(minPos == 1000001){
            timeComputer[iter->second].push(-computers.size());
            if(timeComputer[iter->second].top() == -computers.size())
                update(iter->second, computers.size());
            
            computers.push_back(1);
            endTimes.push_back(iter->second);
        }
        else{
            ++computers[minPos];
            timeComputer[endTimes[minPos]].pop();
            
            if(!timeComputer[endTimes[minPos]].empty())
                update(endTimes[minPos], -timeComputer[endTimes[minPos]].top());
            else
                update(endTimes[minPos], 1000001);
            
            timeComputer[endTimes[minPos]=iter->second].push(-minPos);
            if(timeComputer[iter->second].top() == -minPos)
                update(iter->second, minPos);
        }
    }
    
    printf("%d\n", computers.size());
    for(auto iter = computers.begin(); iter != computers.end(); ++iter)
        printf("%d ", *iter);
        
    return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;

#define pii pair<int,int>

int n, f, k, num, delName[1000001], delPtr, fwTree[1000010];
char command;

void update(int num, int val){
    while(num<=n)
        fwTree[num] += val, num += (num & -num);
}

int getSum(int ed){
    int res = 0;
    while(ed)
        res += fwTree[ed], ed -= (ed & -ed);
    return res;
}

int bs(int val){
    int l=1, r=n, m;
    while(l<=r){
        m=(l+r)/2;
        if(getSum(m)<=val) l=m+1;
        else r=m-1;
    }
    return l;
}

int main()
{
    scanf("%d%d%d",&n,&f,&k); ++f; getchar();
    for(int cnt=1; cnt<=n; ++cnt)
        update(cnt, 1);
    
    for(int cnt=0; cnt<k; ++cnt){
        scanf("%c",&command);
        switch(command){
        case 'U':
            scanf("%d",&num); getchar();
            f = bs(getSum(f)-num-1);
        break;
        
        case 'D':
            scanf("%d",&num); getchar();
            f = bs(getSum(f)+num-1);
        break;
        
        case 'C':
            getchar();
            delName[delPtr] = f;
            
            if(f==bs(n-delPtr-1)) f = bs(getSum(f)-2);
            else f = bs(getSum(f));
            
            update(delName[delPtr++], -1);
        break;
        
        case 'Z':
            getchar();
            update(delName[--delPtr],1);
        break;
        }
    }
    
    sort(delName, delName+delPtr);
    for(int cnt=0; cnt<delPtr; ++cnt)
        printf("%d\n",delName[cnt]-1);
        
    return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int campus[11][11], n, m;
vector<pair<int, pair<int, int>>> bridges;

//2차원 배열의 유효한 위치인 지 확인하는 함수
bool canGotoPos(int x, int y){
	return 0<=x && x<n && 0<=y && y<m;
}

//dfs 건물, 다리 탐색용
int dx[]={1,-1,0,0}, dy[]={0,0,1,-1}, bCnt;
void dfs(int x, int y, int mode, int val){
	
	//건물 탐색용
	if(mode == -1){
		campus[x][y] = val;
		
		//4방향으로 뻗어가면서 더 이어진 부분이 있는 지 확인함
		for(int cnt=0;cnt<4;++cnt){
			int nx = x+dx[cnt], ny = y+dy[cnt];
			if(canGotoPos(nx, ny) && campus[nx][ny] == -1)
				dfs(nx, ny, mode, val);
		}
	}
	
	//다리 탐색용
	else{
		int nx = x+dx[mode], ny = y+dy[mode];
		if(canGotoPos(nx, ny)){
			
			//다음 지점이 빈 공간이면 한칸 더감
			if(campus[nx][ny] == 0)
				dfs(nx, ny, mode, val+1);
			
			//다음 지점이 자기 건물이 아니면서 거리가 1보다 크면 벡터에 저장. min,max는 나중에 중복된 다리를 없애기 위함임
			else if(campus[nx][ny] != bCnt && val>1)
				bridges.push_back(make_pair(val, make_pair(min(bCnt, campus[nx][ny]), max(bCnt, campus[nx][ny]))));
			
		}
	}
}

//union-find 함수
int group[7];
int findGroup(int bNum){
	if(bNum == group[bNum]) return bNum;
	return group[bNum] = findGroup(group[bNum]);
}

 
int main() {
	scanf("%d%d",&n,&m);
	for(int nCnt = 0; nCnt<n; ++nCnt)
		for(int mCnt = 0; mCnt<m; ++mCnt){
			scanf("%d",&campus[nCnt][mCnt]);
			//건물의 번호가 1번부터 시작하므로 건물의 존재여부와 건물번호에 차이를 두기 위해 건물의 존재여부는 -1로 저장함
			campus[nCnt][mCnt] = -campus[nCnt][mCnt];
		}
	
	//dfs를 통해 건물 특정짓기
	int totalBuilding = 0;
	for(int nCnt = 0; nCnt<n; ++nCnt)
		for(int mCnt = 0; mCnt<m; ++mCnt)
			
			//방문한 지점에 번호가 매겨지지 않은 건물이 있으면 건물에 번호를 붙여줌
			if(campus[nCnt][mCnt] == -1) 
				dfs(nCnt, mCnt, -1, ++totalBuilding);
			
	
	//dfs를 통해 각 건물을 연결하는 다리 만들기. bCnt는 dfs()에서도 사용됨
	for(bCnt = 1; bCnt<=totalBuilding; ++bCnt)
		for(int nCnt = 0; nCnt<n; ++nCnt)
			for(int mCnt = 0; mCnt<m; ++mCnt)
				
				//방문한 지점이 건물이면 한 방향으로 다리를 놓아봄
				if(campus[nCnt][mCnt] == bCnt)
					for(int cnt=0; cnt<4; ++cnt)
						dfs(nCnt, mCnt, cnt, 0);
				
	
	//unoin-find 초기 세팅
	for(int cnt=1; cnt<=6; ++cnt)
		group[cnt] = cnt;
	
	//중복된 다리 제거
	sort(bridges.begin(), bridges.end());
	bridges.erase(unique(bridges.begin(), bridges.end()),bridges.end());
	
	//최소 스패닝 트리를 이용한 간선 채택
	int matchCnt=1, result=0;
	for(int cnt=0; cnt<bridges.size(); ++cnt){
		int val = bridges[cnt].first, x = bridges[cnt].second.first, y = bridges[cnt].second.second;
		
		//채택된 두 건물이 서로 다른 그룹이면 다리를 선택함
		if(findGroup(x) != findGroup(y))
			group[findGroup(y)] = findGroup(x), ++matchCnt, result+=val;
		
		//모든 건물이 한 그룹으로 묶였으면 다리 선택을 그만둠.
		if(matchCnt == totalBuilding) break;
	}
	
	//모든 건물이 하나로 묶였으면 result, 아니면 불가능하다는 뜻이므로 -1을 출력
	printf("%d",matchCnt==totalBuilding?result:-1);

	return 0;
}

#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;

#define pii pair<int, int>

int n, h, result;

//histograms에는 항상 오름차순 높이만 존재하게끔 만듦 (뽑을 때는 내림차순으로 나옴)
stack<pii> histograms;

int main() {
	scanf("%d",&n);
	for(int cnt=0;cnt<n;++cnt){
		scanf("%d",&h);
		
		int possiblePtr = cnt;		
		while(!histograms.empty() && h<=histograms.top().first){
			pii histogram = histograms.top(); histograms.pop();
			
			//현재 높이에서 가능한 넓이와 result를 비교함
			result = max(result, h*(cnt-histogram.second+1));
			
			//스택에 있던 first는 현재 높이 h에서는 불가능하므로 h이전 위치까지의 넓이와 result를 비교함
			//이게 가능한 이유는 histograms가 오름차순으로 들어가 있기 때문에 넓이가 보장됨.
			result = max(result, histogram.first*(cnt-histogram.second));
			
			//h보다 크거나 같은 높이값이기 때문에 second(=first 높이의 시작점)부터 최소 h만큼의 높이를 보장함
			possiblePtr = histogram.second;
		}
		histograms.push(make_pair(h,possiblePtr));
	}
	
	//마지막으로 스택에서 빠지지 않은 (높이,시작점)들을 빼면서 최대값을 갱신함.
	while(!histograms.empty()){
		pii histogram = histograms.top(); histograms.pop();
		result = max(result, histogram.first*(n-histogram.second));
	}
	
	printf("%d",result);
	return 0;
}

/*
모든 경우의 수를 탐색?
N^2이므로 10000000000 백억이므로 해결 불가
분할 정복 활용을 활용하자!
사각형이 왼쪽, 오른쪽, 걸쳐있을 케이스 고려
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> heights;

//left ~ right까지 찾을 수 있는 사각형 중 가장 큰 사각형 반환
int search(int left, int right){
	if(left == right){//base
		return heights[left];
	}
	int mid = (left + right) / 2;
	//왼쪽, 오른쪽
	int ret = max(search(left, mid), search(mid+1, right));
	
	
	//걸쳐있을 케이스
	int height = min(heights[mid], heights[mid+1]);
	ret = max(ret, height * 2);
	int l_idx = mid;
	int r_idx = mid + 1;
	while(left < l_idx || r_idx < right){
		if(r_idx < right && (l_idx == left || heights[l_idx - 1] < heights[r_idx + 1])){
			r_idx++;
			height = min(height, heights[r_idx]);
		}else{
			l_idx--;
			height = min(height, heights[l_idx]);
		}
		
		ret = max(ret, height * (r_idx - l_idx + 1));
	}
	return ret;
}

int main(){
	cin >> N;
	heights.resize(N);
	for(int i = 0; i < N; i++){
		cin >> heights[i];
	}
	cout << search(0 , N-1);
	return 0;
}

#include <iostream>
using namespace std;

int paper[10][10];
int colorpaper[5] = { 0,0,0,0,0 };
int answer = 26;

bool is_square(int x, int y, int n)
{
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (paper[x + i][y + j] == 0)
				return false;
		}
	}
	return true;
}

void glue(int x, int y, int count) {
	while (paper[x][y] == 0) {
		y++;
		if (y == 10) {
			x++;
			if (x == 10){
				if (count < answer)
					answer = count;
				return;
			}
			y = 0;
		}
	}
	if (answer <= count)
		return;

	for (int i = 5; i > 0; i--) {
		if (x + i <= 10 && y + i <= 10 && colorpaper[i] < 5 && is_square(x, y, i) == true) {
			for (int j = 0; j < i; j++) {
				for (int k = 0; k < i; k++) {
					paper[x + j][y + k] = 0;
				}
			}
			colorpaper[i]++;
			glue(x, y, count + 1);
			for (int j = 0; j < i; j++) {
				for (int k = 0; k < i; k++) {
					paper[x + j][y + k] = 1;
				}
			}
			colorpaper[i]--;
		}
	}
}

int main() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++)
			cin >> paper[i][j];
	}

	glue(0, 0, 0);

	if (answer > 25)
		answer = -1;

	cout << answer << endl;

	return 0;
}