시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
7 초 512 MB 154 26 8 25.806%

문제

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 수열의 모든 수는 1 이상 N 이하이며 서로 다르다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 

  • l r k: 부분배열 [Al, Al+1, ..., Ar] 을 k만큼 오른쪽으로 시프트한다. 고로, Al 은 Al+k, Ar-k 는 Ar, Ar-k+1 은 Al, Ar 은 Al+k-1 이 된다. 이후, 수열에 길이 3의 증가하는 부분 수열 (subsequence) 이 있다면 YES, 아니면 NO를 출력한다. 

입력

첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 120,000)

둘째 줄에는 A1, A2, ..., AN이 주어진다. 모든 수는 서로 다르다. (1 ≤ Ai ≤ N)

셋째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 120,000)

넷째 줄부터 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (1 ≤ L ≤ R ≤ N, 0 ≤ K ≤ R-L+1)

출력

쿼리의 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

6
2 5 6 1 3 4
1
1 6 5

예제 출력 1

YES

예제 입력 2

8
5 1 2 8 7 6 3 4
4
2 4 2
4 5 1
1 3 2
3 8 2

예제 출력 2

YES
YES
YES
YES

예제 입력 3

5
4 3 2 5 1
2
3 4 1
1 2 1

예제 출력 3

NO
YES

예제 입력 4

6
6 5 4 3 2 1
3
1 1 0
1 3 1
2 5 3

예제 출력 4

NO
NO
YES
W3sicHJvYmxlbV9pZCI6IjE3OTYxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMjE4XHVjNWY0XHVhY2ZjIFx1Y2ZmY1x1YjlhYyAzNSIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZTM4XHVjNzc0XHVhYzAwIE5cdWM3NzggXHVjMjE4XHVjNWY0IEE8c3ViPjE8XC9zdWI+LCBBPHN1Yj4yPFwvc3ViPiwgLi4uLCBBPHN1Yj5OPFwvc3ViPlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjMjE4XHViMjk0IDEgXHVjNzc0XHVjMGMxIE4gXHVjNzc0XHVkNTU4XHVjNzc0XHViYTcwJm5ic3A7XHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC4mbmJzcDtcdWM3NzRcdWI1NGMsIFx1YjJlNFx1Yzc0YyBcdWNmZmNcdWI5YWNcdWI5N2MgXHVjMjE4XHVkNTg5XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuJm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGNvZGU+bCByIGs8XC9jb2RlPjogXHViZDgwXHViZDg0XHViYzMwXHVjNWY0IFtBPHN1Yj5sPFwvc3ViPiwgQTxzdWI+bCsxPFwvc3ViPiwgLi4uLCBBPHN1Yj5yPFwvc3ViPl0gXHVjNzQ0IGtcdWI5Y2NcdWQwN2MgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YzJkY1x1ZDUwNFx1ZDJiOFx1ZDU1Y1x1YjJlNC4gXHVhY2UwXHViODVjLCBBPHN1Yj5sPFwvc3ViPiBcdWM3NDAgQTxzdWI+bCtrPFwvc3ViPiwgQTxzdWI+ci1rPFwvc3ViPiBcdWIyOTQgQTxzdWI+cjxcL3N1Yj4sIEE8c3ViPnItaysxPFwvc3ViPiBcdWM3NDAgQTxzdWI+bDxcL3N1Yj4sIEE8c3ViPnI8XC9zdWI+IFx1Yzc0MCBBPHN1Yj5sK2stMTxcL3N1Yj4gXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVjNzc0XHVkNmM0LCBcdWMyMThcdWM1ZjRcdWM1ZDAgXHVhZTM4XHVjNzc0IDNcdWM3NTggXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjQgKHN1YnNlcXVlbmNlKSBcdWM3NzQgXHVjNzg4XHViMmU0XHViYTc0IDxjb2RlPllFUzxcL2NvZGU+LCBcdWM1NDRcdWIyYzhcdWJhNzQgPGNvZGU+Tk88XC9jb2RlPlx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxzZWN0aW9uIGlkPVwiaW5wdXRcIj5cclxuPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyMThcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMjAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IEE8c3ViPjE8XC9zdWI+LCBBPHN1Yj4yPFwvc3ViPiwgLi4uLCBBPHN1Yj5OPFwvc3ViPlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWMyMThcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC4gKDEmbmJzcDsmbGU7IEE8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyZuYnNwO04pPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZmZjXHViOWFjXHVjNzU4IFx1YWMxY1x1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBNICZsZTsgMTIwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMTM3XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNmZmNcdWI5YWNcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEwgJmxlOyZuYnNwO1IgJmxlOyBOLCAwJm5ic3A7JmxlOyBLJm5ic3A7JmxlOyBSLUwrMSk8XC9wPlxyXG48XC9zZWN0aW9uPlxyXG4iLCJvdXRwdXQiOiI8c2VjdGlvbiBpZD1cIm91dHB1dFwiPlxyXG48cD5cdWNmZmNcdWI5YWNcdWM3NTggXHVhY2IwXHVhY2ZjXHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48XC9zZWN0aW9uPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzk2MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBKdW1wIGZyb20gSGVpZ2h0IG9mIFNlbGYtaW1wb3J0YW5jZSB0byBIZWlnaHQgb2YgSVEgTGV2ZWwiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBuIHNreXNjcmFwZXJzIGFycmFuZ2VkIGluIGEgcm93LCB0aGUgaGVpZ2h0IG9mIHRoZSBpLXRoIG9mIHRoZW0gaXMgaDxzdWI+aTxcL3N1Yj4uIFRoZSBudW1iZXJzIGg8c3ViPmk8XC9zdWI+IGZvcm0gYSBwZXJtdXRhdGlvbiBvZiBpbnRlZ2VycyBmcm9tIDEgdG8gbi48XC9wPlxyXG5cclxuPHA+QWxleGV5IHdhbnRzIHRvIG1ha2UgYSBqdW1wIHVzaW5nIGhpcyBncmFwcGxpbmcgaG9vay4gSW4gb3JkZXIgdG8gcGVyZm9ybSBhIGp1bXAsIGhlIG5lZWRzIGV4YWN0bHkgdGhyZWUgc2t5c2NyYXBlcnM6IGksIGosIGssIHN1Y2ggdGhhdCBpICZsdDsgaiAmbHQ7IGsgYW5kIGg8c3ViPmk8XC9zdWI+ICZsdDsgaDxzdWI+ajxcL3N1Yj4gJmx0OyBoPHN1Yj5rPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+SW4gYWRkaXRpb24sIHNreXNjcmFwZXJzIHNvbWV0aW1lcyBjaGFuZ2UgdGhlaXIgcG9zaXRpb25zLiBZb3UgaGF2ZSB0byBoYW5kbGUgcSBxdWVyaWVzOjxcL3A+XHJcblxyXG48cD5JbiB0aGUgaS10aCBxdWVyeSB5b3UgYXJlIGdpdmVuIGw8c3ViPmk8XC9zdWI+LCByPHN1Yj5pPFwvc3ViPiwgazxzdWI+aTxcL3N1Yj4uIFNreXNjcmFwZXIgZnJvbSBldmVyeSBwb3NpdGlvbiBqIHN1Y2ggdGhhdCBsPHN1Yj5pPFwvc3ViPiAmbGU7IGogJmxlOyByPHN1Yj5pPFwvc3ViPiZtaW51cztrPHN1Yj5pPFwvc3ViPiBtb3ZlcyB0byBwb3NpdGlvbiBqICsgazxzdWI+aTxcL3N1Yj4sIGFuZCBza3lzY3JhcGVyIGZyb20gZXZlcnkgcG9zaXRpb24gaiBzdWNoIHRoYXQgcjxzdWI+aTxcL3N1Yj4gJm1pbnVzOyBrPHN1Yj5pPFwvc3ViPiArIDEgJmxlOyBqICZsZTsgcjxzdWI+aTxcL3N1Yj4gbW92ZXMgdG8gcG9zaXRpb24gaiArIGs8c3ViPmk8XC9zdWI+ICZtaW51czsgKHI8c3ViPmk8XC9zdWI+ICZtaW51czsgbDxzdWI+aTxcL3N1Yj4gKyAxKS4gSW4gb3RoZXIgd29yZHMsIHlvdSBuZWVkIHRvIHNoaWZ0IHRoZSBzZWdtZW50IGw8c3ViPmk8XC9zdWI+LCAuIC4gLiAsIHI8c3ViPmk8XC9zdWI+IG9mIHRoZSBza3lzY3JhcGVycyBjeWNsaWNhbGx5IHRvIHRoZSByaWdodCBraSB0aW1lcy48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgZWFjaCBxdWVyeSwgaGVscCBBbGV4ZXkgdG8gZGV0ZXJtaW5lIHdoZXRoZXIgaGUgY2FuIHBlcmZvcm0gYSBqdW1wIG9yIG5vdC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgMTIwIDAwMCksIHRoZSBudW1iZXIgb2Ygc2t5c2NyYXBlcnMuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBuIGludGVnZXJzIGg8c3ViPmk8XC9zdWI+ICgxICZsZTsgaDxzdWI+aTxcL3N1Yj4gJmxlOyBuKSwgdGhlIGhlaWdodHMgb2YgdGhlIHNreXNjcmFwZXJzLiBUaGUgbnVtYmVycyBoPHN1Yj5pPFwvc3ViPiBhcmUgcGFpcndpc2UgZGlzdGluY3QuPFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIHEgKDEgJmxlOyBxICZsZTsgMTIwIDAwMCksIHRoZSBudW1iZXIgb2YgcXVlcmllcy48XC9wPlxyXG5cclxuPHA+TmV4dCBxIGxpbmVzIGNvbnRhaW4gZGVzY3JpcHRpb25zIG9mIHF1ZXJpZXM6IHRoZSBpLXRoIG9mIHRoZW0gY29udGFpbnMgdGhyZWUgcG9zaXRpdmUgaW50ZWdlcnMgbDxzdWI+aTxcL3N1Yj4sIHI8c3ViPmk8XC9zdWI+LCBrPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGw8c3ViPmk8XC9zdWI+ICZsZTsgcjxzdWI+aTxcL3N1Yj4gJmxlOyBuLCAwICZsZTsgazxzdWI+aTxcL3N1Yj4gJmxlOyByPHN1Yj5pPFwvc3ViPiAmbWludXM7IGw8c3ViPmk8XC9zdWI+ICsgMSkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcXVlcnksIHByaW50IGEgc2luZ2xlIHdvcmQgb24gYSBzZXBhcmF0ZSBsaW5lOiAmbGRxdW87WUVTJnJkcXVvOyBpZiB0aGVyZSBhcmUgc3VpdGFibGUgc2t5c2NyYXBlcnMgdG8gcGVyZm9ybSBhIGp1bXAsIGFuZCAmbGRxdW87Tk8mcmRxdW87IG90aGVyd2lzZS48XC9wPlxyXG4iLCJoaW50IjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9mNTE2YTI3Zi0yMmUyLTQ3NzctOWFlNS0wNmIyYmI5OGYzZTZcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDY0MHB4OyBoZWlnaHQ6IDM2MHB4O1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Camp > Petrozavodsk Programming Camp > Summer 2019 > Day 9: MEX Foundation Contest D번

  • 문제를 만든 사람: jatana
  • 문제를 번역한 사람: koosaga