시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 950 278 175 33.270%

문제

자연수 \(n\)개로 이루어진 배열 \(a_1,a_2,a_3,\dots ,a_n\)이 있다.

\(l\)부터 \(r\)까지 부분 배열은 \(a_l,a_{l+1},\dots , a_r\) 이다.

\(K_s\)는 부분 배열 안에 있는 자연수 \(s\)의 개수이다.

부분 배열의 힘이란 모든 자연수 \(s\)에 대해서, \(K_s \cdot K_s \cdot s\)를 합한 값이다.

배열과 부분 배열의 범위가 주어졌을 때, 각 부분 배열의 힘을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 \(n\)과 부분 배열의 개수 \(t\)가 주어진다. (1 ≤ \(n\), \(t\) ≤ 105) 둘째 줄에는 \(n\)개의 자연수 \(a_i\) (1 ≤ \(a_i\) ≤ 106) 가 주어진다.

다음 \(t\)개 줄에는 부분 배열의 범위 \(l_i\)와 \(r_i\)가 주어진다. (1 ≤ \(l_i\) ≤ \(r_i\) ≤ \(n\))

출력

입력으로 주어지는 각 부분 배열의 힘을 출력한다.

예제 입력 1

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

예제 출력 1

28
25
21
W3sicHJvYmxlbV9pZCI6Ijg0NjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMzBcdWM1ZjRcdWM3NTggXHVkNzk4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3OTBcdWM1ZjBcdWMyMTggXFwoblxcKVx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYzMwXHVjNWY0IFxcKGFfMSxhXzIsYV8zLFxcZG90cyAsYV9uXFwpXHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XFwobFxcKVx1YmQ4MFx1ZDEzMCBcXChyXFwpXHVhZTRjXHVjOWMwIFx1YmQ4MFx1YmQ4NCBcdWJjMzBcdWM1ZjRcdWM3NDAgXFwoYV9sLGFfe2wrMX0sXFxkb3RzICwgYV9yXFwpIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XFwoS19zXFwpXHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWJjMzBcdWM1ZjQgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggXFwoc1xcKVx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmQ4MFx1YmQ4NCBcdWJjMzBcdWM1ZjRcdWM3NTggXHVkNzk4XHVjNzc0XHViNzgwIFx1YmFhOFx1YjRlMCBcdWM3OTBcdWM1ZjBcdWMyMTggXFwoc1xcKVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFxcKEtfcyBcXGNkb3QgS19zIFxcY2RvdCBzXFwpXHViOTdjIFx1ZDU2OVx1ZDU1YyBcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMzMFx1YzVmNFx1YWNmYyBcdWJkODBcdWJkODQgXHViYzMwXHVjNWY0XHVjNzU4IFx1YmM5NFx1YzcwNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDEgXHViZDgwXHViZDg0IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWQ3OThcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgXFwoblxcKVx1YWNmYyBcdWJkODBcdWJkODQgXHViYzMwXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOCBcXCh0XFwpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBcXChuXFwpLCBcXCh0XFwpICZsZTsgMTA8c3VwPjU8XC9zdXA+KSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFxcKG5cXClcdWFjMWNcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4IFxcKGFfaVxcKSAoMSAmbGU7IFxcKGFfaVxcKSAmbGU7IDEwPHN1cD42PFwvc3VwPikgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFxcKHRcXClcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWJjMzBcdWM1ZjRcdWM3NTggXHViYzk0XHVjNzA0IFxcKGxfaVxcKVx1YzY0MCBcXChyX2lcXClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFxcKGxfaVxcKSAmbGU7IFxcKHJfaVxcKSAmbGU7IFxcKG5cXCkpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFjMDEgXHViZDgwXHViZDg0IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWQ3OThcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg0NjIiLCJwcm9ibGVtX2xhbmciOiIzIiwidGl0bGUiOiJQb3RcdTAxMTlcdTAxN2NuYSB0YWJsaWNhIiwiZGVzY3JpcHRpb24iOiI8cD5EYW5hIGplc3QgdGFibGljYSBcXChuXFwpIGxpY3piIG5hdHVyYWxueWNoIFxcKGFfMSxhXzIsYV8zLFxcZG90cyAsYV9uXFwpLiBSb3p3YVx1MDE3Y215IGZyYWdtZW50IHRlaiB0YWJsaWN5IG9kIFxcKGxcXCktdGVnbyBkbyBcXChyXFwpLXRlZ28gZWxlbWVudHU6IFxcKGFfbCxhX3tsKzF9LFxcZG90cyAsIGFfclxcKS4gT3puYWN6bXkgcHJ6ZXogXFwoS19zXFwpIGxpY3piXHUwMTE5IHd5c3RcdTAxMDVwaWVcdTAxNDQgbGljemJ5IFxcKHNcXCkgdyB0eW0gZnJhZ21lbmNpZS4gUG90XHUwMTE5Z1x1MDEwNSBmcmFnbWVudHUgdGFibGljeSBuYXp5d2FteSBzdW1cdTAxMTkgaWxvY3p5biZvYWN1dGU7dyBcXChLX3MgXFxjZG90IEtfcyBcXGNkb3Qgc1xcKSBwbyB3c3p5c3RraWNoIGxpY3piYWNoIG5hdHVyYWxueWNoIFxcKHNcXCkuIE9ibGljeiBwb3RcdTAxMTlnaSBwb2RhbnljaCBmcmFnbWVudCZvYWN1dGU7dy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlcgcGllcndzenltIHdpZXJzenUgd2VqXHUwMTViY2lhIHpuYWpkdWpcdTAxMDUgc2lcdTAxMTkgZHdpZSBsaWN6YnkgY2FcdTAxNDJrb3dpdGUgXFwoblxcKSBpIFxcKHRcXCkgKDEgJmxlOyBcXChuXFwpLCBcXCh0XFwpICZsZTsgMTA8c3VwPjU8XC9zdXA+KSBvem5hY3phalx1MDEwNWNlIGRcdTAxNDJ1Z29cdTAxNWJcdTAxMDcgdGFibGljeSBcXChhXFwpIG9yYXogbGljemJcdTAxMTkgZnJhZ21lbnQmb2FjdXRlO3csIGRsYSBrdCZvYWN1dGU7cnljaCBuYWxlXHUwMTdjeSBvYmxpY3p5XHUwMTA3IHBvdFx1MDExOWdpLiBEcnVnaSB3aWVyc3ogemF3aWVyYSBcXChuXFwpIGxpY3piIG5hdHVyYWxueWNoIFxcKGFfaVxcKSAoMSAmbGU7IFxcKGFfaVxcKSAmbGU7IDEwPHN1cD42PFwvc3VwPikuIEthXHUwMTdjZHkgeiBrb2xlam55Y2ggXFwodFxcKSB3aWVyc3p5IG9waXN1amUgamVkbmVuIGZyYWdtZW50LiBPcGlzIGZyYWdtZW50dSBza1x1MDE0MmFkYSBzaVx1MDExOSB6IGR3Jm9hY3V0ZTtjaCBsaWN6YiBjYVx1MDE0Mmtvd2l0eWNoIFxcKGxfaVxcKSwgXFwocl9pXFwpICgxICZsZTsgXFwobF9pXFwpICZsZTsgXFwocl9pXFwpICZsZTsgXFwoblxcKSksIGt0Jm9hY3V0ZTtyZSBvem5hY3phalx1MDEwNSBpbmRla3MgamVnbyBsZXdlZ28gaSBwcmF3ZWdvIGtyYVx1MDE0NGNhLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk5hIHd5alx1MDE1YmNpdSBuYWxlXHUwMTdjeSB3eXBpc2FcdTAxMDcgXFwodFxcKSB3aWVyc3p5LCB3IFxcKGlcXCktdHltIHNwb1x1MDE1YnImb2FjdXRlO2QgbmljaCBwb3dpbm5hIHpuYWxlXHUwMTdhXHUwMTA3IHNpXHUwMTE5IGplZG5hIGxpY3piYSBjYVx1MDE0Mmtvd2l0YSByJm9hY3V0ZTt3bmEgcG90XHUwMTE5ZHppZSBcXChpXFwpLXRlZ28geiBwb2RhbnljaCBmcmFnbWVudCZvYWN1dGU7dy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQzZjRcdWI3ODBcdWI0ZGNcdWM1YjQifV0=

출처

Camp > POI Training Camp > ONTAK 2011 6-2번