문제
길이가 $N$인 수열 $A_1, \cdots, A_N$이 주어집니다. 수열의 모든 수는 서로 다른 1ドル$ 이상 $N$ 이하의 수입니다. 아래 조건을 모두 만족시키는 $(i, j)$ 정수쌍의 개수를 구하세요.
- 1ドル \le i \le j \le N$.
- $A$의 $i$번째 수부터 $j$번째 수까지가 오름차순으로 배열되어있다. 즉, $i \le k < j$를 만족하는 모든 정수 $k$에 대해 $A_k < A_{k+1}$.
출력
문제의 조건을 만족시키는 $(i, j)$ 정수쌍의 개수를 출력하세요.
문제의 조건을 만족시키는 $(i, j)$와 해당하는 $i$번째 수부터 $j$번째까지 수는 다음과 같습니다.
- $(1, 1) - [1]$
- $(1, 2) - [1, 2]$
- $(1, 3) - [1, 2, 5]$
- $(2, 2) - [2]$
- $(2, 3) - [2, 5]$
- $(3, 3) - [5]$
- $(4, 4) - [4]$
- $(5, 5) - [3]$
W3sicHJvYmxlbV9pZCI6IjMxMzk1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjODE1XHViODJjXHViNDFjIFx1YzVmMFx1YzE4ZFx1ZDU1YyBcdWJkODBcdWJkODRcdWMyMThcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFlMzhcdWM3NzRcdWFjMDAgJE4kXHVjNzc4IFx1YzIxOFx1YzVmNCAkQV8xLCBcXGNkb3RzLCBBX04kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gXHVjMjE4XHVjNWY0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWMyMThcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCAkMSQgXHVjNzc0XHVjMGMxICROJCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjMjE4XHVjNzg1XHViMmM4XHViMmU0LiBcdWM1NDRcdWI3OTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWI5Y2NcdWM4NzFcdWMyZGNcdWQwYTRcdWIyOTQgJChpLCBqKSQgXHVjODE1XHVjMjE4XHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JDEgXFxsZSBpIFxcbGUgaiBcXGxlIE4kLjxcL2xpPlxyXG5cdDxsaT4kQSRcdWM3NTggJGkkXHViYzg4XHVjOWY4IFx1YzIxOFx1YmQ4MFx1ZDEzMCAkaiRcdWJjODhcdWM5ZjggXHVjMjE4XHVhZTRjXHVjOWMwXHVhYzAwIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWJjMzBcdWM1ZjRcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuIFx1Yzk4OSwgJGkgXFxsZSBrICZsdDsgaiRcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWMyMTggJGskXHVjNWQwIFx1YjMwMFx1ZDU3NCAkQV9rICZsdDsgQV97aysxfSQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NCAkTiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiAkKDEgXFxsZSBOIFxcbGUgMjAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhYzAxIFx1YzZkMFx1YzE4YyAkQV8xLCBBXzIsIFxcY2RvdHMsIEFfTiRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICQoMSBcXGxlIEFfaSBcXGxlIE47JCAkQV8xLCBBXzIsIFxcY2RvdHMsIEFfTiRcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM4MTVcdWMyMTgkKSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YjI5NCAkKGksIGopJCBcdWM4MTVcdWMyMThcdWMzMGRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzEzOFx1YzY5NC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+XHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWMyZGNcdWQwYTRcdWIyOTQgJChpLCBqKSRcdWM2NDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0ICRpJFx1YmM4OFx1YzlmOCBcdWMyMThcdWJkODBcdWQxMzAgJGokXHViYzg4XHVjOWY4XHVhZTRjXHVjOWMwIFx1YzIxOFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjMmI1XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiQoMSwgMSkgLSBbMV0kPFwvbGk+XHJcblx0PGxpPiQoMSwgMikgLSBbMSwgMl0kPFwvbGk+XHJcblx0PGxpPiQoMSwgMykgLSBbMSwgMiwgNV0kPFwvbGk+XHJcblx0PGxpPiQoMiwgMikgLSBbMl0kPFwvbGk+XHJcblx0PGxpPiQoMiwgMykgLSBbMiwgNV0kPFwvbGk+XHJcblx0PGxpPiQoMywgMykgLSBbNV0kPFwvbGk+XHJcblx0PGxpPiQoNCwgNCkgLSBbNF0kPFwvbGk+XHJcblx0PGxpPiQoNSwgNSkgLSBbM10kPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIzMTM5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik51bWJlciBvZiBTb3J0ZWQgQ29udGlndW91cyBTdWJzZXF1ZW5jZXMiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gYSBzZXF1ZW5jZSAkQV8xLCBcXGNkb3RzLCBBX04kIG9mIGxlbmd0aCAkTiQuIEFsbCBudW1iZXJzIGluIHRoZSBzZXF1ZW5jZSBhcmUgZGlzdGluY3QgaW50ZWdlcnMgYmV0d2VlbiAkMSQgYW5kICROJCBpbmNsdXNpdmUuIEZpbmQgdGhlIG51bWJlciBvZiBwYWlycyBvZiBpbnRlZ2VycyAkKGksIGopJCB0aGF0IHNhdGlzZnkgYWxsIHRoZSBjb25kaXRpb25zIGJlbG93LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiQxIFxcbGUgaSBcXGxlIGogXFxsZSBOJC48XC9saT5cclxuXHQ8bGk+U3RhcnRpbmcgZnJvbSB0aGUgJGkkLXRoIG51bWJlciB0byB0aGUgJGokLXRoIG51bWJlciwgdGhlIG51bWJlcnMgaW4gJEEkIGFyZSBzb3J0ZWQgaW4gYXNjZW5kaW5nIG9yZGVyLiBUaGF0IGlzLCBGb3IgYWxsIGludGVnZXJzICRrJCBzYXRpc2Z5aW5nICRpIFxcbGUgayAmbHQ7IGokLCAkQV9rICZsdDsgQV97aysxfSQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zICROJCwgdGhlIGxlbmd0aCBvZiB0aGUgc2VxdWVuY2UuICQoMSBcXGxlIE4gXFxsZSAyMDBcXCwwMDApJDxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGVhY2ggZWxlbWVudCBvZiB0aGUgc2VxdWVuY2UgJEFfMSwgQV8yLCBcXGNkb3RzLCBBX04kIHNlcGFyYXRlZCBieSBzcGFjZXMuICQoMSBcXGxlIEFfaSBcXGxlIE47JCAkQV8xLCBBXzIsIFxcY2RvdHMsIEFfTiQgYXJlIGRpc3RpbmN0IGludGVnZXJzJCkkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIG51bWJlciBvZiBwYWlycyBvZiBpbnRlZ2VycyAkKGksIGopJCB3aGljaCBzYXRpc2Z5Jm5ic3A7dGhlIGNvbmRpdGlvbnMgZ2l2ZW4gaW4gdGhlIHByb2JsZW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5UaGUgJChpLCBqKSQgcGFpcnMgc2F0aXNmeWluZyB0aGUgY29uZGl0aW9ucyBnaXZlbiBpbiB0aGUgcHJvYmxlbSBhbmQgdGhlaXIgY29ycmVzcG9uZGluZyBjb250aWd1b3VzIHN1YnNlcXVlbmNlIGZyb20gdGhlICRpJC10aCBudW1iZXIgdG8gdGhlICRqJC10aCBudW1iZXIgYXJlIGFzIGZvbGxvd3MuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JCgxLCAxKSAtIFsxXSQ8XC9saT5cclxuXHQ8bGk+JCgxLCAyKSAtIFsxLCAyXSQ8XC9saT5cclxuXHQ8bGk+JCgxLCAzKSAtIFsxLCAyLCA1XSQ8XC9saT5cclxuXHQ8bGk+JCgyLCAyKSAtIFsyXSQ8XC9saT5cclxuXHQ8bGk+JCgyLCAzKSAtIFsyLCA1XSQ8XC9saT5cclxuXHQ8bGk+JCgzLCAzKSAtIFs1XSQ8XC9saT5cclxuXHQ8bGk+JCg0LCA0KSAtIFs0XSQ8XC9saT5cclxuXHQ8bGk+JCg1LCA1KSAtIFszXSQ8XC9saT5cclxuPFwvdWw+XHJcbiJ9XQ==